네발로 코딩하는 포메라니안

1. 문제 2. 풀이 과정 def solution(people, limit): answer = 0 people.sort() l = 0 r = len(people)-1 while l < r: #2명씩 타는 경우 count if people[l]+people[r]

1. 문제 2. 풀이 과정 방법 1) 시간 초과 number에서 k개를 뺏을 때 len(number) - k 길이의 수를 만들어야 한다. 이 조건에서 첫 번째 자리가 될 수 있는 수는 뒤에서 count 했을 때, 원하는 길이 이상인 값들이 그 후보이다. 최댓값과 그의 index값을 따로 찾는 데에 시간이 오래 걸렸다고 판단하였다. def solution(number, k): answer = '' pre_idx = -1 for i in range(1, len(number)-k+1)[::-1]: #이전에 선택한 값의 뒤부터 길이에 맞는 곳까지 중 최대값 찾기 answer += max(number[pre_idx+1:len(number)-i+1]) pre_idx = number[pre_idx+1:len(numb..

1. 문제 2. 풀이 과정 이 문제에서 답이 될 수 있는 후보는 두 가지이다. 1. 첫 번째는 단순히 index 0번에서 끝까지 차례대로 가면서 알파벳을 맞춰주는 것이다. 2. 두 번째는 제일 긴 A들의 연속을 피해서 둘러가는 것이다. A가 있는 건 굳이 갈 필요가 없는 곳이다. 제일 긴 A들의 연속만 피하고 짧은 A연속은 무시하는 이유는 예를 들어 설명하겠다. "KFPWAAAOFAAAAAALFJ"이라는 문자열이 입력으로 들어왔다고 할 때, 굵은 글자는 무조건 가야 하는 곳이다. OF로 가기 위해서는 짧은 A의 연속을 지나가는 것이 더 빠른 길이다. 정리하자면, A를 피해가는 방법 중에서는 제일 긴 A들의 연속을 피해 가는 것이 제일 빠른 방법이 된다. 또 여기서 "KFPWAAAOFAAAAAALFJ" 형..

1. 문제 2. 풀이 과정 방법 1) for문으로 자신보다 작은 수로 나눠지는지 하나씩 검사하여 소수를 판별하였다. def prime(n): #소수여부 검사 if n

1. 문제 2. 풀이 과정 방법 1) 이진탐색을 사용한다. 최소값 즉, start = 0이고 최대는 가능한 n편의 최대가 배열의 길이이므로 end = l로 설정하였다. def solution(citations): citations.sort() l = len(citations) s = 0 e = l #최댓값 while s

1. 문제 2. 풀이 과정 개인적으로 테스트 케이스들을 생각해보는 게 알고리즘을 떠올리기가 좋았다. [CASE1] 두 수 비교부터 생각해보면, [35, 3443]이 있다고 가정하자. 참고로, 숫자와 달리 문자열은 아스키코드에 따라 인덱스 0번째부터 비교해간다. 오름차순으로 정렬하면 [3443, 35]가 되며 큰 수부터 나열하면 정답인 "353443"을 반환한다. [CASE2] 그러면 [34, 3421]인 경우를 생각해보자. 이미 정렬된 상태로 정답인 "343421"과 다른 "342134"를 반환한다. 여기 문제는 34의 자릿수가 적어서 발생한다. 문자열 정렬과 위 문제는 이 부분에서 차이가 난다. 결론 CASE1)처럼 자릿수가 끝나기 전에 그 자릿수까지의 숫자가 달라서 정렬이 되면 상관없지만, 그 자릿수..

1. 문제 2. 풀이과정 방법 1) heapq 내장 모듈 활용 import heapq def solution(scoville, K): answer = 0 heapq.heapify(scoville) while scoville[0] < K: if len(scoville) == 1: return -1 answer += 1 #가장 안매운거, 두 번째 안매운거 heap에서 빼서 연산 a = heapq.heappop(scoville) + heapq.heappop(scoville)*2 #섞은거 넣기 heapq.heappush(scoville, a) return answer 방법 2) heapq대신 deque만 이용하였다. 섞은 결과는 새로운 배열 mix에 따로 저장하여 scoville와 mix의 맨 앞 원소만 비교하..

1. 문제 2. 풀이 과정 방법 1) 직관적으로 생각나는 방법, 자신보다 뒤에 있는 값을 하나씩 확인해서 계산한다. 시간복잡도 O(%{n}^2%) def solution(prices): answer = [] for i in range(len(prices)): for j in range(i+1, len(prices)): if prices[i] > prices[j]: answer.append(j-i) break if len(answer)-1 < i: answer.append(len(prices)-1-i) return answer 방법 2) stack을 이용해서 더 빨리 계산한다. 코드 실행 과정 예시 입력 : [1, 2, 3, 2, 1] stack [(1, 0)] [(1, 0), (2, 1)] [(1, 0)..

1. 문제 2. 풀이과정 방법 1) 큐에 [트럭 무게, 위치]를 넣고, 반복문 한 번 돌 때마다 위치를 1 감소시켜서 위치 값이 1이 되면 트럭이 다리에서 나간다. 변수 c는 다음에 기다리는 트럭의 truck_weights에서의 인덱스 값을 나타낸다. from collections import deque def solution(bridge_length, weight, truck_weights): answer = 1 Q = deque() #다리 Q.append([truck_weights[0], bridge_length]) sum = truck_weights[0] c = 1 while Q: answer += 1 if Q[0][1] == 1:#다리 출발(bridge_length)에서 끝(1)까지 도착하면 po..

1. 문제 2. 풀이 과정 방법 1) 큐에서 하나 꺼낼 때마다 location을 1 감소시켜서 현재 위치를 업데이트한다. from collections import deque def solution(priorities, location): Q = deque() for i in priorities: Q.append(i) count = 0 while Q: a = Q.popleft() if Q and a < max(Q): Q.append(a) else: count += 1 if location == 0: return count location -= 1 if location < 0 : location = len(Q)-1 return count 방법 2) 큐에 처음 인덱스 정보와 데이터를 함께 저장하고, any를..