코딩테스트 준비 - 더 맵게

다시푸는 코딩 테스트 준비 일지

• 응시 사이트 : 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. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

2. 스코빌 지수가 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;
}

코드 결과 - 벡터 체크