Programmers 코딩 테스트 연습 힙(Heap) 라면공장 정답.

import heapq

def solution(stock, dates, supplies, k):
    answer, idx = 0, 0
    pq = []
    while stock < k:
    	# stock과 보급 전까지 버틸 수 있는 날자는 같다.
        for current in range(idx, len(dates)):
        # idx는 소진되지 않은 dates와 stock의 idx를 의미한다.
            if dates[current] <= stock:
            # 사용 가능한 자원이면 pq에 넣는다.
            # heapq는 최소 힙이므로, -로 넣어야 우선순위가 높아진다.
                heapq.heappush(pq, -supplies[current])
            # 썼으니 다음 idx부터 다음에 찾아본다.
                idx = current +1
            else:
            # 아직 이 idx의 자원이 available 하지 않으면 다음에 check한다.
                idx = current
                break
        print(pq)
        answer += 1
        # 뺄 때 - 해주는거 잊지 말자. (음수로 push)
        stock += -heapq.heappop(pq)
    return answer

이 문제는 정말 해결하면서 애먹었다... ㅠㅠ

 

솔직히 자바 언어로는 정말 쉽게 풀었는데...

파이썬으로 푸니까 정말 칼같은 케이스를 만족시키지 않으면 안되더라...

 

두 언어의 채점 기준이 다른것 같다.

 

원래는 미리 pq에 정렬해두고, day 기준에 맞게 pop해서 사용하려 했는데, 시간 초과가 나버렸다...

 

즉, pq에서 넣고 빼는 연산까지도 최소화해야 하는 채점 조건을 갖고 있는 것이다... ㅠㅠ

 

시간 복잡도는 nlogn (n은 dates, supplies의 배열 length)가 되겠다.

 

사실 바깥의 stock 조건도 고려해줘야 하지만...

 

이 문제의 경우는 단순히 시간복잡도를 낮추는 것만으로는 만점이 안나온다 ㅋㅋ

최대한 순수 default 연산의 수를 줄여주어야만 정답이 나오는 것 같다.