프로그래머스 / 더 맵게

https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

 

문제 요약 >

음식들의 매운 정도가 주어진다. 모든 음식의 매운 정도가 특정값 이상이 되도록 정해진 방법으로 섞자. 최소 몇 회를 섞어야 하는가?

 

풀이 >

힙(Heap)으로 분류되어있는 문제이고, 해당 문제에서는 음식들의 '맵기'라는 우선순위가 존재하므로, 우선순위 큐를 떠올렸다. 우선순위 큐는 일반적으로 힙을 이용해서 구현 가능하다. 힙은 부모노드와 자식노드의 대소관계가 성립하는 특성을 가지는 트리인데, 완전이진트리의 특성상 부모 노드에서 자식 노드로 가는 방법은 i * 2 혹은 i * 2 + 1이고, 자식 노드에서 부모 노드로 가는 방법은 i / 2이다. push 혹은 pop을 할 때는 부모노드와 자식노드만 비교하면 되고, 조건에 어긋나는 경우 만족할때까지 부모노드와의 자리를 계속 바꿔주면 된다.

 

요론 개념을 이해한 상태에서, 풀이는 priority_queue 사용..!

 

 

> 첫번째 풀이 : 문제 분류를 신경쓰지 않고 vector만을 이용해 풀어보았다. 여러번의 sort, erase가 발생한다.

결과 - 효율성 테스트 fail

 #include <string>
 #include <vector>
 #include <algorithm>
 #include <iostream>

 using namespace std;

 int solution(vector<int> scoville, int K) {
     int answer = 0;
     int newComp = 0;

     sort(scoville.begin(), scoville.end());

     while (scoville[0] < K && scoville.size() > 1) {
         newComp = scoville[0] + scoville[1] * 2;
         scoville[1] = newComp;

         scoville.erase(scoville.begin());

         sort(scoville.begin(), scoville.end());
         answer++;
     }

     if (scoville.size() == 1 && scoville[0] < K) answer = -1;

     return answer;
 }

 

> 두번째 풀이 : 우선순위 큐를 이용해서 풀이했다. 주의할 점 : 큐는 탐색(검색)이 불가능하다는 점을 기억하자. index를 통해 접근하는 방법 뿐만 아니라 iterator도 존재하지 않으며 심지어 find함수도 쓸 수 없다.

결과 - pass

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int elem1, elem2, newComp;
    
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < scoville.size(); i++) {
        pq.push(scoville[i]);
    }
    
    while (pq.top() < K && pq.size() > 1) {
        elem1 = pq.top(); pq.pop();
        elem2 = pq.top(); pq.pop();
        
        newComp = elem1 + elem2 * 2;
        pq.push(newComp);
        answer++;
    }

    if (pq.size() == 1 && pq.top() < K) answer = -1;
    
    return answer;
}