문제
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다.
모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.
제한 사항
- scoville의 길이는 2 이상 1,000,000 이하입니다.
- K는 0 이상 1,000,000,000 이하입니다.
- scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
- 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
입출력 예
입출력 예 설명
- 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12] - 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
가진 음식의 스코빌 지수 = [13, 9, 10, 12]
모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.
해결 방법
우선순위 큐를 사용한다면 간단하게 풀리는 문제다.
우선순위 큐가 힙(Heap)이라는 자료구조로 구현되어있기 때문에 프로그래머스 상에서 분류는 힙으로 되어있다.
먼저 모든 음식의 스코빌 지수를 우선순위 큐에 삽입한다.
priority_queue<int, vector<int>, greater<int> > pq;
우선순위 큐를 위와 같이 선언하면 오름차순 정렬이 되도록 구현할 수 있다.
그리고 큐를 돌면서 가장 앞의 원소가 K이상이 됐는지 확인하고, 그렇다면 그 뒤의 음식들도 전부 스코빌 지수가 K보다 크다는 뜻이기 때문에 정답을 출력하고 종료하면 된다.
하지만 맨 앞의 원소가 K 미만이라면 Leo가 개발한 특별한 방법으로 새로운 음식을 만들어서 큐에 다시 삽입하면 된다.
예를 들어, 현재 음식의 스코빌 지수가 [1, 2, 3, 9, 10, 12]이고 K = 7인 경우
맨 앞의 원소인 1이 7보다 작기 때문에 1과 2를 뽑아서 1 + 2*2 = 5를 큐에 삽입한다.
이후 큐의 원소는 [3, 5, 9, 10, 12]이다.
다시 맨 앞의 원소인 3이 7보다 작으므로 3과 5를 뽑아서 3 + 2*5 = 13을 큐에 삽입한다.
이후 큐의 원소는 [9, 10, 12, 13]이다.
이제 맨 앞의 원소인 9가 7보다 커졌으므로 정답을 출력하고 프로그램을 종료한다.
효율성 테케도 다 맞았는데 정확성 테케 16번이 자꾸 틀렸다고 떠서 뭐가 잘못됐나 봤더니
원소가 한개이고 그게 K보다 작은 경우가 주어졌을때 세그멘테이션 오류가 나고 있었다.
예를 들어, 음식의 스코빌 지수가 [7]이고 K = 8인 경우
맨 앞의 원소인 7이 8보다 작으므로 -1을 출력하고 프로그램을 종료하면 된다.
큐 탐색을 시작하면서 바로 맨 앞의 원소를 뽑아버리는데 내가 종료 조건을 (현재 큐의 사이즈 == 1) && (가장 앞의 원소 < K)로 설정해둔 탓에 제대로 종료가 되지 못하고 에러가 났던 것,,,
이 조건만 (현재 큐의 사이즈 == 0) && (가장 앞의 원소 < K)로 바꿔줬더니 통과!
if(pq.empty() && top < K) {
return -1;
}
내 코드
#include <string>
#include <vector>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > pq;
int solution(vector<int> scoville, int K) {
int answer = 0;
for(int i = 0; i < scoville.size(); i++) {
pq.push(scoville[i]);
}
while(!pq.empty()) {
int top = pq.top();
pq.pop();
if(pq.empty() && top < K) {
return -1;
}
if(top >= K) {
break;
}
else {
answer++;
int second = pq.top();
pq.pop();
pq.push(top + 2* second);
}
}
return answer;
}