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

문제 링크

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

 

문제 설명

1. 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다.
2. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
3. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
4. Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
5. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때
6. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

 

문제 입출력 예)

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

 

문제 풀이(1/2) - 음수를 활용한 방법

주어진 scoville 위의 배열을 내림차순으로 정렬 한 뒤, 첫번째 배열의 위치 + 두번째 배열*2의 위치를 계산한다.

계산한 배열은 pop을 시키고, 새로 생성된 배열을 push를 시키는 과정을 거친다.

반복횟수는 첫번째 배열의 값이 K보다 크거나 같은 경우까지 반복하도록 한다.

아래의 경우가 가능하도록 하려면 priority_queue를 사용해야한다. 하지만, 우선순위 que는 큰 수로 정렬이 되기 때문에 -를 붙여 음수로 변형시키거나, greater<int>를 사용해서 값을 할당하도록 하자.

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int temp = 0;
    priority_queue<int> q;
    for(auto s:scoville){
        q.push(-s);
    }
    
    while(-q.top() < K){
        temp = -q.top(); q.pop();
        if(q.empty()) return -1;
        temp = q.top()*-2 + temp;
        q.pop(); q.push(-temp);
        answer++;    
    }    
    return answer;
}

 

문제 풀이(2/2) - 양수를 넣고 오름차순으로 정렬

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int temp = 0;
    
    priority_queue<int,vector<int>,greater<int>> q (scoville.begin(),scoville.end());
    
    while(q.top() < K){
        temp = q.top(); q.pop();
        if(q.empty()) return -1;
        temp = q.top()*2 + temp;
        q.pop(); q.push(temp);
        answer++;    
    }    
    return answer;
}

 

 

리뷰

priority_queue의 존재는 다익스트라알고리즘 공부할 때 알고 있었던 내용이다.

하지만, 음수를 붙여서 작은수가 나오도록 하는 방법만 있는지 알았다.

priority_queue<int, vector<int>, greater<int>> pq (scoville.begin(), scoville.end()); 식으로

사용할 수 있다는 것을 공부하는 시간이 되었다.