코딩테스트 연습 : 힙 - 더 맵게

Checking·2021년 3월 17일

coding test

Programmers 코딩테스트 연습

목록 보기

9/20

💻 더 맵게

분류 : Heap (힙)

사용 언어 : C++

문제 링크

🤔 문제 이해

문제 설명

매운 것을 좋아하는 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 )

Priority Queue를 사용한다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    int times = 0;
    priority_queue <int, vector<int>, greater<int>> foods (scoville.begin(), scoville.end());
    // 우선순위 큐, pop시 작은 값이 추출되도록 greater<int> 형태로 정렬함.

    while (foods.top() < K) {
        // 우선순위 큐 속의 가장 작은 스코빌 지수 값이 기준점 K보다 작을 시 계속 실행
        
        if (foods.size() < 2) return -1;
        // 만약 스코빌 지수가 작은데 음식이 한 가지라 섞을 수 없다면 -1을 리턴한다. 

        // 섞어주는 과정, 가장 작은 값과 두번째로 작은 값을 꺼내 공식대로 더해주고 push
        int food_1 = foods.top();
        foods.pop();

        int food_2 = foods.top();
        foods.pop();

        foods.push(food_1 + food_2 * 2);

        times++;	// 섞은 횟수 ++
    }

    return times;
}

/*
정확성  테스트
    테스트 1 〉	통과 (0.01ms, 3.72MB)
    테스트 2 〉	통과 (0.01ms, 3.68MB)
    테스트 3 〉	통과 (0.01ms, 3.95MB)
    테스트 4 〉	통과 (0.01ms, 3.95MB)
    테스트 5 〉	통과 (0.01ms, 3.95MB)
    테스트 6 〉	통과 (0.08ms, 3.93MB)
    테스트 7 〉	통과 (0.06ms, 3.93MB)
    테스트 8 〉	통과 (0.02ms, 3.96MB)
    테스트 9 〉	통과 (0.01ms, 3.94MB)
    테스트 10 〉	통과 (0.06ms, 3.93MB)
    테스트 11 〉	통과 (0.04ms, 3.93MB)
    테스트 12 〉	통과 (0.12ms, 3.83MB)
    테스트 13 〉	통과 (0.07ms, 3.95MB)
    테스트 14 〉	통과 (0.01ms, 3.82MB)
    테스트 15 〉	통과 (0.09ms, 3.97MB)
    테스트 16 〉	통과 (0.01ms, 3.93MB)

효율성  테스트
    테스트 1 〉	통과 (26.22ms, 8.93MB)
    테스트 2 〉	통과 (52.81ms, 14MB)
    테스트 3 〉	통과 (205.90ms, 39.2MB)
    테스트 4 〉	통과 (20.23ms, 7.81MB)
    테스트 5 〉	통과 (220.95ms, 40.8MB)

채점 결과
    정확성: 76.2
    효율성: 23.8
    합계: 100.0 / 100.0
*/