[프로그래머스] 더 맵게 in C++

(제가 생각한 솔루션이므로 최적의 솔루션이 아닐 수 있습니다..! 피드백 환영합니다!)

 

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

1. 문제 이해

문제에서 주어지는 입력값은 총  두 개입니다.

 

입력값 이름	예시	타입	조건
scoville	[1, 1, 2, 2, 3]	vector<int>	길이: 2 이상 1,000,000 이하
K	3	int	0 이상 1,000,000,000 이하

 

scoville 내 가장 값이 작은 원소 두 개를 다음과 같은 규칙으로 새로운 원소를 만들게 됩니다.

 

새로운 원소 = 가장 작은 원소 + 두 번째로 작은 원소 * 2

 

새로운 원소를 만들고 다시 scoville 벡터에 집어넣습니다.

 

scoville 벡터 내 모든 원소가 K 값 이상일 때까지 위 과정을 반복하고 그 반복 횟수를 반환해야 합니다.

만약 위 과정을 끝까지 반복해도 K 이상이 안될 경우, -1을 반환해야 합니다.

 

2. 풀이법 연상

scoville 벡터의 가장 작은 값들에 대해서 계속해서 끄집어내고 연산한 뒤에 다시 집어넣고 다시 정렬하는 방식으로 알고리즘을 짜야 하는 것을 생각할 수 있었습니다.

 

위 알고리즘을 위해서 사용할 수 있는 편리한 자료구조는 최소힙, 또는 우선 순위 큐가 있습니다.

 

위 자료구조를 사용해서 가장 작은 두 수를 꺼내고 섞은 뒤에 다시 집어넣어서 벡터 내 가장 작은 수가 K 이상인지 확인하는 과정을 구현하기로 했습니다.

 

섞을 수 있는 음식이 하나 밖에 남지 않았을 때, 그리고 그 음식이 K 보다 작을 경우에는 -1을 반환해주도록 처리하면 됩니다.

 

3.  풀이에 필요한 지식

최소힙은 이진 트리 구조로 되어있으며, 부모 노드가 자식 노드보다 크지 않도록 되어 있습니다.

 

이진 트리구조이기 때문에 삽입과 삭제 모두 O(log N) 시간복잡도를 가집니다.

이는 일반적으로 정렬을 이용해서 최소값을 삽입하고 정렬하고 삭제하는 과정보다 더 빠르기 때문에 이러한 과정을 자주 이용하게 될 것 같은 경우, 힙 구조를 사용하는 것이 매우 좋습니다!

 

위 힙 구조를 통해서 우선순위 큐를 구현할 수 있습니다!

 

우선순위 큐는 말 그대로 Queue 구조와 동일하지만 어떤 우선순위 규칙에 의해 내부 원소들이 정렬되는 자료구조입니다.

 

이번 문제에는 최소값이 가장 먼저 나오게 되는, 즉 오름차순으로 정렬된 우선순위 큐를 구현하면 유용하게 사용할 수 있을 것입니다.

 

C++의 STL  중 queue 라이브러리에 우선순위 큐가 구현되어있습니다.

 

아래 코드는 1, 3, 2, 4를 차례대로 우선순위 큐에 입력하고 top의 원소를 차례대로 출력하면서 pop하는 코드입니다.

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> pq;
    pq.push(1);
    pq.push(3);
    pq.push(2);
    pq.push(4);
    
    while(!pq.empty()){
        cout << pq.top() << ' '; // 4 3 2 1 
        pq.pop();
    }
    return 0;
}

 

위 출력 내용을 보면, 기본적으로 우선순위 큐는 내림차순으로 설정되는 것을 확인할 수 있습니다.

 

만약 이번 문제와 같이 오름차순으로 구현해야 한다면 다음과 같이 구현할 수 있습니다.

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(2);
    
    while(!pq.empty()){
        cout << pq.top() << ' '; // 1 2 3 4
        pq.pop();
    }
    return 0;
}

 

4. 코딩

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for (auto & elem : scoville){
        pq.push(elem);
    }

    while(pq.top() < K){
        if(pq.size() == 1){
            return -1;
        }
        int temp1 = pq.top(), temp2;
        pq.pop();
        temp2 = pq.top();
        pq.pop();
        pq.push(temp1 + temp2 * 2);
        answer++;
    }
    
    return answer;
}