[CodingTest] 프로그래머스 Programmers 힙 Level 2 더 맵게

풀이

파이썬에는 heapify 메서드가 있고 최소힙으로 구현해준다. 

힙은 오랜만에 봐서 개념이 가물가물했는데 개념을 보니 대충 생각이 났다.

힙의 좋은 점은 스택, 큐와 다르게 push와 pop을 하면 바로 자동으로 최소힙으로 정렬해준다는 점!

너무 편리한 것 같다.

하지만 스택, 큐, 힙... 실력이 부족하여 문제에 적합한 자료구조를 파악하는 것은 어려운 것같다.

(사실 자료구조 알아도 적용하는 것만도 힘듦 ㅋ..)

 

k는 스코빌 지수로, 모든 값을 k이상으로 만드는 것이 목표인 문제다. (불가능하면 -1 리턴)

처음에 scoville[0]<k 부분에서 min함수를 사용했었는데 효율이 좋지 않게 나와 수정했다.

알고리즘

 

1) heapify를 사용하여 최소힙으로 만들어준다.

2) scoville 리스트에 2개 이상의 값이 있다면, 앞의 두값을 pop한다. (a, b)

3) new_num에 문제에서 제시한 계산법을 적용한 값을 넣어준다.

4) scoville 리스트에 new_num 값을 넣어준다.

5) 횟수를 나타내는 answer 값을 1 증가한다.

6) scoville 리스트에 2개 미만의 값, 즉 1개 혹은 0개의 값이 있다면, while 문에서 첫 값이 k 보다 작은 값임을 판단하기 때문에, scoville의 첫 값이 k보다 작고 원소가 1 혹은 0개 이므로 계산할 방법이 더 이상 존재하지 않아 모든 원소를 k 이상으로 만들 수 없다. 따라서 -1을 리턴한다.