다시푸는 코딩 테스트 준비 일지
응시 사이트 : Programmers
문제 : 더 맵게
사용언어 : C++
난이도 : 중
풀이시간 : 41m
유형 : 힙, 우선순위 큐
문제 설명
매운 것을 좋아하는 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 합니다.
입출력 예
scoville K return
[1, 2, 3, 9, 10, 12] 7 2
입출력 예 설명
스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
가진 음식의 스코빌 지수 = [13, 9, 10, 12]
모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.
문제 풀이 접근
이 문제는, 스코빌 지수가 가장 낮은 2개를 섞어서 새로운 것을 만들어 내, 최종적으로 모든 요소를 K 이상의 스코빌로 만들 수 있느냐, 없느냐, 있다면 최소 몇번 섞어야 하느냐가 핵심인 문제다.
가장 먼저 떠올린 것은, 당연하게도 인자로 벡터를 줬기 때문에, O(n^2) 이 될 수 있을만한 코드를 작성했다.
유효성 테스트가 없을줄 알고 진행했고, 다른 유형 다맞췄는데 효율성 5개 전부다 실패했다.
이후, AI 코드 문제 힌트가 있어서 바로 확인해서 문제를 다르게 세팅하여 풀이를 진행했다.
AI 힌트 : Heap, Priority Queue는 삽입부터 값이 정렬되어 순회할 필요가 없다. 지금 너의 코드는 벡터로 계속 순회해서 찾는데 너무 비효율 적이다. 그러니, 힙이나 우선순위 큐를 써봐라.
내 선택은 우선순위 큐를 세팅하여 작성하였다.
우선순위 큐의 Greater 만 세팅하면 우선순위 큐의 값은 오름차순으로 매칭된다.
결국 오름차순이기 때문에 여기서 top 의 값과 K 만 비교해서 크다면 자료구조의 성격으로 나머지는 K 보다 크다는 것이 보장된다는 것을 키로 잡아서 문제를 해결했다.
이 문제의 해결 플로우,
1. scovile 로 들어온 값들을 전부 우선순위 큐로 세팅한다. (greater 까지 세팅한다.)
2.인자 배열에 장난치는 케이스들을 예상해서 앞 예외를 모두 처리해준다.
( 미리 K 값 이상인데 들어온다거나, 배열이 0 이라거나, 등등 )
3. while 루프를 돌며 top 원소를 체크하고, 내부에서 가장 낮은 원소 2개를 빼주는데, 1개 빼줄때마다 pq의 사이즈를 체크한다.
(1개가 들어올 수도 있기때문에..)
4. pq.top() < K 의 값을 기준으로 while 루프를 잡았으니, 최종 횟수를 구한다면 알아서 answer 를 Return 값으로 반환하고 종료된다.
정답 작성 코드 (C++)
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int solution(vector<int> scoville, int K) {
int answer = 0;
priority_queue<int,vector<int>, greater<int>> pq;
for (int i = 0; i < scoville.size(); ++i)
{
pq.push(scoville[i]);
}
if (scoville.size() == 0)
return -1;
bool check = true;
for (int i = 0; i < scoville.size(); ++i)
{
if (scoville[i] < K)
{
check = false;
break;
}
}
if (check == true)
return answer;
int newScovile = 0;
while (pq.top() < K)
{
newScovile = 0;
check = true;
auto fst = pq.top();
if (pq.size() == 0)
return -1;
pq.pop();
auto snd = pq.top();
if (pq.size() == 0)
return -1;
pq.pop();
newScovile = (fst + (snd * 2));
pq.push(newScovile);
// 새로운 스코빌 지수 추가
++answer;
}
return answer;
}코드 결과
오답 작성 코드 (C++) - 맨 처음 벡터 기준으로 체크 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> scoville, int K) {
int answer = 0;
if (scoville.size() == 0)
return -1;
bool check = true;
for (int i = 0; i < scoville.size(); ++i)
{
if (scoville[i] < K)
{
check = false;
break;
}
}
if (check == true)
return answer;
int lessFst = 2000000000;
int lessFstIdx = -1;
int lessSnd = 2000000000;
int lessSndIdx = -1;
int newScovile = 0;
while (check == false)
{
newScovile = 0;
lessFst = 2000000000;
lessSnd = 2000000000;
lessFstIdx = -1;
lessSndIdx = -1;
check = true;
for (int i = 0; i < scoville.size(); ++i)
{
if (lessFst > scoville[i])
{
lessFst = scoville[i];
lessFstIdx = i;
}
}
scoville.erase(scoville.begin()+ lessFstIdx, scoville.begin()+ lessFstIdx+1);
for (int i = 0; i < scoville.size(); ++i)
{
if (lessSnd > scoville[i])
{
lessSnd = scoville[i];
lessSndIdx = i;
}
}
scoville.erase(scoville.begin() + lessSndIdx, scoville.begin() + lessSndIdx + 1);
if (lessFst == 2000000000)
return -1;
if (lessSnd == 2000000000)
return -1;
newScovile = (lessFst + (lessSnd * 2));
scoville.push_back(newScovile);
// 새로운 스코빌 지수 추가
for (int i = 0; i < scoville.size(); ++i)
{
if (K > scoville[i])
{
check = false;
break;
}
}
++answer;
}
return answer;
}코드 결과 - 벡터 체크
