코딩테스트 연습> 힙(Heap)> 더 맵게

 

<문제링크: https://programmers.co.kr/learn/courses/30/lessons/42626>

코딩테스트 연습 - 더 맵게

 

문제설명: scoville 배열에 스코빌 지수가 주어지고, 이 중 가장 맵지 않은 지수와 두 번째로 맵지 않은 지수 즉 가장 낮은 숫자 2개를 뽑아 (최소값+ 두 번째 최소값*2)을 다시 scoville 배열에 넣어주기를 반복한다. 이를 모든 스코빌 지수가 주어진 변수 K보다 큰 값이 될 때까지 반복하면 된다. 단, 모든 변환을 마치고도 K보다 작은 값이 남아있다면 -1을 return 한다.

 

[1차 시도]

import heapq
def solution(scoville, K):
    answer = 0
    while min(scoville) < K:
        a = heapq.heappop(scoville)
        b = heapq.heappop(scoville)
        heapq.heappush(scoville, a+b*2)
        answer+=1
    if max(scoville)<K:
        return -1
    return answer

 

풀이: scoville의 모든 원소가 K보다 커지도록 scoville의 min값을 찾아 K보다 작을 경우에만 반복을 했다. 반복문을 돌면서 scoville을 heap해주고 2번의 최소값을 a와 b로 저장하고 계산한 새로운 스코빌지수를 heappush로 추가해주었다. 그리고 실행 횟수를 1씩 증가시켰다. while문을 다 돌고 scoville의 최대값이 K보다 크면 -1을 반환했다.

 

채첨결과: 정확성 42.9점과 효율성 0점으로 fail이다. 정확성의 반은 런타임 에러가 나고 효율성 testcase 5개는 전부 시간초과다. 사실 시간복잡도의 개념을 잘 몰라서 처음엔 그냥 무작정 sort와 min max, pop과 append를 썼다. 그러면 전부 통과가 안돼서 이번 기회에 heapq의 활용법을 익힐 수 있었다.

 

*이제 와서 보니 이 풀이에 오류가 있는게 scoville의 최소값이 K보다 작을 동안 while문 반복인데 이는 -1을 반환하는 경우인 K보다 작은 수가 있는 경우와의 모순이 발생한다.

 

해결방법: while 문의 scoville min값 찾기와 예외 처리 max값 찾기의 시간복잡도는 O(N)이므로 상당한 시간이 걸린다는 의미다. 해결방법을 찾아보다가 heapify()라는 함수를 발견했다. heapify()란 기존에 주어진 배열을 힙으로 변환하는 것이다. heapify()의 시간복잡도는 최악의 경우 트리의 높이에 해당되는 O(logN) 이 된다.

 

 

[2차 시도]

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while scoville[0] < K:
        a = heapq.heappop(scoville)
        b = heapq.heappop(scoville)
        heapq.heappush(scoville, a+b*2)
        answer+=1
    if max(scoville)<K:
        return -1
    return answer

 

풀이: 위와 동일한 코드에 처음 scoville만 힙으로 만들어주고 scoville의 첫 번째 원소를 기준으로 while 문을 반복한다.

 

채첨결과: 정확성 57.1 효율성 23.8으로 정확성 testcase 4개에서 런타인 에러가 난다.

 

해결방법: 아무래도 while문에서 계속 시간 초과가 나는 것 같다. 모든 testcase에서 scoville[0]가 K보다 작아진다는 보장이 없기 때문에 열심히 구글링을 통해 while문을 scoville의 길이만큼 돌려주어야 한다는 힌트를 살짝 얻었다.

 

 

[3차 시도]

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while len(scoville) >= 2:
        a = heapq.heappop(scoville)
        b = heapq.heappop(scoville)
        heapq.heappush(scoville, a+b*2)
        answer+=1
        if scoville[0] >= K:
            return answer
    return -1

 

풀이: scoville 배열에서 적어도 2개의 원소를 뽑아 진행해야하므로 scoville 길이가 2이상일 때만 while문을 반복했다. 반복문을 계속 돌면서 scoville의 0번째 인덱스로 최소값을 찾아 만약 K 이상이 된다면 그 때의 실행 횟수를 return한다. while문이 return 없이 무사히(?) 통과됐다면, 스코빌 지수 중 K보다 작은 값이 있다는 것이므로 -1을 반환해 예외처리를 해주었다.

 

채첨결과: 정확성과 효율성 모두 잘 통과한다. YAYYY!!