![]()
min heap에서 2가지 원소를 pop 하고 a + 2 * b 의 등식을 적용 후 push 하는 문제였다. 파이썬의 heapq를 처음 사용해보았다. 파이썬의 heapq의 경우 일반 리스트를 min heap 처럼 사용할 수 있게 해주는 라이브러리이다. heapq.heapify(list): list가 min heap으로 변한다. (O(N), 제자리에서 정렬) heapq.heappop(list): heapify된 list에서 min 값을 리턴. heapq.heappush(list, item) push의 경우 이론에서 배웠던 heapify를 자동으로 수행해준다. 0번 인덱스에는 가장 작은 값, n번 인덱스의 2n + 1 인덱스에는 left child, 2n + 2 인덱스에는 right child ( paren..
![]()
시간 초과 답안. 비효율적으로 비교가 일어남 대략 생각해보면 복잡도 O(N^2) 효율성 테스트 1, 2, 3, 4를 모두 통과하지 못했다. def solution(prices): answer = [[0, False] for _ in prices] # q = deque(answer) # print(q) # print(q) for i, p in enumerate(prices): for j in range(i): if answer[j][1] == False: answer[j][0] +=1 if prices[j] > p: answer[j][1] = True answer = list(zip(*answer))[0] return answer 이후 문제 분류처럼 스택이나 큐로 풀어봐야겠다 생각하고 고쳐보았다. dequ..
주석을 통해 설명 작성. 데크를 이용하여 큐를 만들어서 품. 현재 문서보다 우선순위 높은 것을 찾을 때 any라는 함수를 이용해서 간결히 푸는 경우도 있었다. from collections import deque def solution(priorities, location): # 우선 순위 값과 인덱스를 데크에 저장. q = deque([ (p,i) for i, p in enumerate(priorities)]) # 문서의 인덱스를 저장해서 출력 순서를 기록. result = [] while len(q) > 0: # f: priority # idx: 문서의 인덱스(priorities list 내에서) f, idx = q.popleft() # 중요도 높은 문서가 있는지 탐색. => any로 하는 풀이도 있..
코딩테스트 고득점 Kit 스택/큐 문제 풀이 import collections def solution(progresses, speeds): # 진행 상황을 기록하는 큐 progress_que = collections.deque(progresses) # progress 증가 속도를 기록하는 큐 speed_que = collections.deque(speeds) days = 0 answer = [] # 큐가 빌 때까지 실행. while len(progress_que): first_feature = progress_que.popleft() speed = speed_que.popleft() # 첫 번째로 큐에 들어간(중요도 높은) 기능이 모두 진행이 된 경우 if speed * days + first_featu..
알고리즘 고득점 Kit 풀이중 .. from collections import deque def solution(bridge_length, weight, truck_weights): answer = 0 on_bridge_w = 0 # 대기 큐 q = deque(truck_weights) # 다리 b = deque() # 현재 시각 sec = 0 while q: # 대기 큐에서 트럭 pop t_w = q.popleft() # 다리 위에 차 있는 경우 제일 먼저 진입한 차량을 다리 길이만큼 움직였는지 확인. # w는 무게, s는 출발 시각 if len(b): w, s = b.popleft() if sec - s != bridge_length: b.appendleft((w,s)) else: on_bridge_..
