Gidhub BE Developer

[Programmers] 42626. 더 맵게

2018-09-28
goodGid

Problem

Problem URL : 더 맵게


[1] Answer Code (18. 09. 28)

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

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int> pq;
    int size = (int) scoville.size();
    
    for(int i=0; i<size; i++){
        pq.push(scoville[i] * -1);
    }
    
    while(! pq.empty()) {
        int first = pq.top(); pq.pop();
        first *= -1;
        if(first >= K )
            break;
        
        if(pq.size() == 0){
            answer = -1;
            break;
        }
        
        int second = pq.top(); pq.pop();
        second *= -1;
        answer++;
        int value = first + (second*2);
        
        // if ( value < K)
        pq.push( value * -1 );

    } // end of while 
    return answer;
}

Review

  • 문제를 정확히 이해 못하고 풀이했더니 1시간이 넘게 걸렸다.

  • 상당히 화가 난다.

  • 여러가지 원인이 있었다.


[1]
for(int i=0; i<size; i++){
    if(scoville[i] < K) // [1]
        pq.push(scoville[i] * -1);
}

가장 처음에 힙에 삽입 작업을 할 때
[1] 조건을 넣었다. 
하지만 그러면 안된다. 
1,3이 주어지고 K가 2라면
1과 3으로 K보다 큰 수를 만들 수 있다.
하지만 [1] 코드를 사용하게 되면
힙에는 1만 존재하고 
1로는 K보다 큰 수를 만들 수 없기 때문에
-1를 반환한다.



[2]
조건 체크 순서를 잘못했다.

q.pop() -> q.size() == 1 
이 순서로 조건을 체크하면 안된다.

힙에 1개가 있을 때
q.pop()을 하게 되면 size는 0이 된다.
즉 [ q.size() == 0 ] 으로 비교를 해야한다.


[3]
힙에 1,3이 있고
K가 2라면
1과 3을 이용해서 K보다 큰 값을 만들 수 있다.
그런데 나는 이미 K보다 큰 수에 대해서는
작업을 할 수 없다 생각하였다.
그렇게 되면 1로는 K를 만들 수 없기 때문에
-1를 리턴한다. 




[4]
 if ( value < K)
    pq.push( value * -1 );

처음에 while문에서 
value = first + second * 2
value값이 K보다 크면 삽입을 안해줬다.
이 또한 [3]문제와 비슷한 오류를 낳게한다.

Comments

Content