[programmers] Lv.2 더 맵게(c++)

1. map을 사용한 풀이

#include <vector>
#include <map>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    map<int, int> scov;
    for(auto s: scoville)
        scov[s]++;
    
    while(scov.begin()->first < K){
        int first = scov.begin()->first;
        scov.begin()->second--;
        if(scov.begin()->second == 0) scov.erase(first);
        
        int second = scov.begin()->first;
        scov.begin()->second--;
        if(scov.begin()->second == 0) scov.erase(second);
        
        scov[first + second*2]++;
        answer++;
        
        if(scov.size() == 1 && scov.begin()->second == 1 && scov.begin()->first < K) return -1;
    }
    
    return answer;
}

 

2. priority_queue를 사용한 풀이

분명 이런 컨테이너가 있었던거같은데 기억이 안나서 map으로 푼 뒤

다른 분들이 priority queue를 사용한것을 보고 priority queue로 새로 푼 풀이이다.

 

#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    priority_queue<int, vector<int>, greater<int>> scov;
    for(auto s: scoville)
        scov.push(s);
    
    while(scov.top() < K){
        int first = scov.top(); scov.pop();
        int second = scov.top(); scov.pop();
        
        scov.push(first + second*2);
        answer++;
        
        if(scov.size() == 1 && scov.top() < K) return -1;
    }
    
    return answer;
}

---

문제

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

코딩테스트 연습 - 더 맵게

728x90

---

[접근] - map

priority queue가 생각이 나질 않았다.

set을 사용할까 했으나, 중복된 숫자가 있을 가능성이 높아서(설명엔 안적혀있었지만) map을 사용했다.

key값으론 스코빌 지수를 value 값으론 해당 스코빌 지수를 가진 음식의 개수를 적었다.

map<int, int> scov;
for(auto s: scoville)
    scov[s]++;

---

[접근1]

map의 default는 key 값이 오름차순으로 정렬된다는것.

map의 맨 앞 값이, 즉 스코빌 지수가 제일 낮은 음식의 스코빌 지수가 주어진 K보다 작으면 음식을 섞는것을 계속 반복한다.

맨 앞의 음식 두개를 first와 second에 담아줬다.

해당 스코빌 지수를 가진 음식의 개수를 하나씩 빼주고, 해당 스코빌 지수를 가진 음식이 0개면 map에서 삭제한다.

while(scov.begin()->first < K){
    int first = scov.begin()->first;
    scov.begin()->second--;
    if(scov.begin()->second == 0) scov.erase(first);

    int second = scov.begin()->first;
    scov.begin()->second--;
    if(scov.begin()->second == 0) scov.erase(second);

    ...
}

---

[접근2]

map에 새로운 음식의 스코빌 지수를 넣어준 뒤, answer 값을 1 증가한다.

만약 map에 하나의 음식밖에 남지 않았는데 스코빌 지수가 K보다 작다면 -1을 리턴해준다

while(scov.begin()->first < K){
    ...

    scov[first + second*2]++;
    answer++;

    if(scov.size() == 1 && scov.begin()->second == 1 && scov.begin()->first < K) return -1;
}

---

[접근] - priority queue

map으로 푼 문제를 제출한 뒤 다른 사람의 코드를 슥 봤더니 priority queue가 보였다

아 내가 찾던 컨테이너가 이거였구나!! 하면서 새로 짰다.

하지만 priority queue는 default가 내림차순이었다. top()을 꺼내면 제일 큰 수가 나왔다..

그래서 vector<int>와 greater<int>를 추가하여 오름차순으로 바꿔주었다.

priority_queue<int, vector<int>, greater<int>> scov;
for(auto s: scoville)
    scov.push(s);

---

[접근1]

제일 작은 스코빌지수의 두개를 first와 second에 담아주었고 queue에서는 제거했다

새로 만든 음식의 스코빌지수를 queue에 넣어줬고 answer값을 1 증가시켰다.

만약 queue에 남은 음식이 하나이고 원하는 K값보다 작다면 -1를 리턴한다.

while(scov.top() < K){
    int first = scov.top(); scov.pop();
    int second = scov.top(); scov.pop();

    scov.push(first + second*2);
    answer++;

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