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]문제와 비슷한 오류를 낳게한다.