[프로그래머스/C++] 더 맵게 풀이

프로그래머스 : 더 맵게

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

프로그래머스

 

문제

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

scoville의 길이는 2 이상 1,000,000 이하입니다.

K는 0 이상 1,000,000,000 이하입니다.

scoville의 원소는 각각 0 이상 1,000,000 이하입니다.

모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

---

풀이 1

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

using namespace std;

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

    while(true){
        sort(scoville.begin(), scoville.end());
        if(scoville[0] >= K){
            break; // 종료
        }
        
        if(scoville.size()<2){
            break; // 종료
        }
        
        // 음식 섞기
        int newSco = scoville[0] + (scoville[1]*2);
        cout << "newSco : " << newSco << endl;
        answer++;
        
        scoville[0] = newSco;
        scoville[1] = newSco;
        scoville.erase(scoville.begin(), scoville.begin()+1);
    }
    
    if (scoville.size() < 2 ) return -1;
    else return answer;
}

에러 메세지

처음에 while 문을 돌아가며 스코빌 지수를 섞고 erase 를 해주었으나 (해당 인덱스의 벡터 원소를 지움),
인덱스도 제대로 지정하기 힘들었고, 무엇보다 시간 초과 문제가 발생했다.

 

 

풀이 2

#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int first, second;
    
    // 오름차순 우선순위 큐
    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){
        answer++;
        first = pq.top();
        pq.pop();
        second = pq.top();
        pq.pop();
        pq.push(first+second*2);
    }
    
    if(pq.top()<K) return -1;
    else return answer;
}

 

해답은 우선 순위 큐 이다.

스코빌 지수가 가장 낮은 두 원소를 pop한 다음, 섞은 스코빌 지수의 음식을 다시 큐에 push한다.

자동으로 오름차순 정렬까지 돼니 코드도 훨씬 간결해져 가독성이 좋아졌다. 👍

 

풀이 인증