[프로그래머스] 더 맵게 [heap, level 2]

 

 

배열 안 모든 숫자들을 K 이상으로 만들어주는 횟수를 구하는 문제

숫자들을 K이상으로 만들 수 없다면 -1을 return 한다.

 

< 코드 1. 실패 >

def solution(scoville, K):
    scoville = sorted(scoville)
    
    cnt = 0
    
    while scoville[0] < K:
        scoville[0] = scoville[0] + scoville[1] * 2
        scoville.pop(1)
        scoville = sorted(scoville)
        cnt += 1
        if scoville[0] < K and len(scoville) == 1 : return -1   
    return cnt
    

제일 작은 숫자만 K이상이 된다면 끝나는 거라 sort 해주고 앞부분만 살펴보면 되겠다 싶었다.

제일 앞(0번)을 계속해서 업데이트를 해주고 뒤에(1번)은 삭제하고 cnt를 늘려 횟수를 세어준다.

if문은 숫자들을 K이상으로 만들 수 없을 때를 체크한 것

K가 0보다 작은데 배열의 길이는 1이면 원하는 대로 만들 수 없으므로 -1을 return 한다.

 

< 결과 > 

 

효율성은 제로

정확성은 다 맞는데 효율성이 떨어져서 오답처리되었다. 아무래도 while문 안에 sorted 함수를 써서 그런 듯한데,
sorted 함수의 시간 복잡도가 O(nlogn)으로 알고 있는데 바깥에 while문까지 돌리니 효율성이 떨어진다.

 

< 코드 2. heap >

효율성 있는 코드를 작성하려면 자료구조를 사용해야 한다.

heap은 삽입, 삭제를 해도 추가적으로 sort를 해 줄 필요가 없어서 효율적이다.

1번 코드에서 매번 sort를 해줘서 효율성이 떨어졌는데 heap을 쓰면 해결된다.

 

heap 중에 min-heap은 부모 노드는 항상 자식 노드에 들어있는 값 보다 작아서 최솟값을 효율적으로 구할 수 있다.

앞에서도 max값을 다룰 일 없이 min값만 달라서 이런 코드를 구현하는 데는 min-heap을 사용해야 한다.

 

나동빈 - 자료구조: 우선순위 큐(Priority Queue)와 힙(Heap) 10분 핵심 요약

 

 

코딩테스트 연습 - 더 맵게