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

 

원래 코드

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

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int> > minSco (scoville.begin(), scoville.end());
    int first, second;
    
    while(true){
        // minSco 길이가 2 이상이고 K 넘음
        if( minSco.size() > 1 && minSco.top() >= K) break;
        
        // minSco 길이가 1인데 K 넘음
        // minSco 길이가 1인데 K 안넘음 -> 절대 넘을 수 없음
        if(minSco.size() == 1){
            if(-minSco.top() >= K) answer += 1;
            else answer = -1;
            break;
        }
        // 아직 K 안넘는 원소 있음
        first = minSco.top();
        minSco.pop();
        second = minSco.top();
        minSco.pop();
        
        minSco.push(first + second*2);
        answer += 1;
    }
    return answer;
}

4가지 경우의 수로 나눴다.

1. minSco 길이가 2 이상이고 모두 K가 넘는 경우

2. minSco 길이가 1이고, K가 안넘는 경우 

3. minSco 길이가 1이고 K가 넘는 경우

4. minSco 길이가 2 이상이고 K가 안넘는 경우

 

이 문제는 절대 queue가 비어있을 수 없다. 왜냐면 1개만 남아도 계속 push하기 때문에 empty()가 true인 경우는 생각하지 않았다.

 

1번 경우에는 섞을 필요가 없으므로 바로 while문 탈출

 

2, 3번에서는  minSco 길이가 1인 경우에는 뽑고 넣어도 결국 자기 자신이다. 그래서 하나 남아있는 값이 K를 넘는지만 확인하면 된다.

만약 K가 안넘으면 아무리 섞어도 K를 넘을 수 없다.

 

4번의 경우 계속 섞어주면 된다.

 

그런데 이렇게 했을 때 테스트 16번만 빼고 효율성까지도 모두 통과했다.

16번 케이스 때문에 자꾸 실패된다. 문제는 너무 조잡스러운 조건문이 남발하는 것 때문이다. 

[1, 2, 3] K=11  인 경우 2가 반환되어야하는데 3번째 경우에 의해서 3이 반환되는 것이었다.

그래서 push를 새로 넣고 다시 K 값과 비교하는 코드를 추가했더니 작동한다.

 

 

성공 코드

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

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int> > minSco (scoville.begin(), scoville.end());
    int first, second;
    
    while(true){
        // minSco 길이가 2 이상이고 K 넘음
        if( minSco.size() > 1 && minSco.top() >= K) break;
        
        // minSco 길이가 1인데 K 넘음
        // minSco 길이가 1인데 K 안넘음 -> 절대 넘을 수 없음
        if(minSco.size() == 1){
            if(-minSco.top() >= K) answer += 1;
            else answer = -1;
            break;
        }
        // 아직 K 안넘는 원소 있음
        first = minSco.top();
        minSco.pop();
        second = minSco.top();
        minSco.pop();
        
        minSco.push(first + second*2);
        answer += 1;
        if(-minSco.top() >= K) break;
    }
    
    return answer;
}

근데 다른사람들의 풀이를 보니까 내 코드가 너무 조잡스러운 것 같다.

그리고 테스트 케이스 중에 [5], K = 5인게 있다. 그러면 안섞어도 되는 거 아닌가.. 

조건들을 확실하게 명시해줬으면 좋겠다.