C++ - 더 맵게

https://school.programmers.co.kr/learn/courses/30/lessons/42626?language=cpp 

프로그래머스

처음에 음식을 섞고 나온 결과 스코빌을 벡터의 원소로 추가하고 다시 오름차순 정렬하는 방식으로 구현했으나

이번 문제는 효율성 테스트가 있어 통과하지 못했습니다.

 

정렬을 없애고 원소를 추가할 때, 자동으로 오름차순이 만들어지게 인덱스를 추가하는 방법도 써보았으니 이 또한 시간 초과로 효율성 테스트를 통과하지 못했습니다.

 

이를 해결하기 위해 검색해보니 정렬 계산 횟수도 적고, 자동 오름차순 정렬이 가능한 우선순위 큐를 찾아 사용했습니다.

 

◈ 우선순위 큐 ( priority_queue )

원소가 삽입될 때 우선순위에 따라 자동 정렬되는 큐( queue )

자료구조 힙(Heap)으로 구현되었기에 원소 삽입(push) 시 정렬은 O(log N) 만에 이루어짐

pop으로 삭제할 시 정렬된 가장 앞의 항목부터

 

선언 : priority_queue<자료형, 컨테이너, 비교 함수> 변수명

 

비교 함수 : 기본 (비교함수를 쓰지 않음) - 내림차순

                   greater<자료형>                   - 오름차순

                   유저 정의 우선순위 - 구조체 활용 및 구조체 연산자 오버로딩, cmp 구조체

                   (유저 정의 우선순위까지 들어가는 건 TMI 같아서 지금은 패스)

 

기본 메서드

push()   : 원소 추가

pop()     : 가장 앞(top) 원소 제거

top()      : 가장 우선순위가 높은 원소

empty() : 큐가 비어있으면 true

size()    : 원소의 수

 

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;

    // 새로운 원소를 받을 때 자동으로 오름차순으로 넣는 우선순위 큐를 사용
    //  = 계산 횟수를 크게 줄이면서 항상 오름차순 유지 > 효율성 테스트
    priority_queue<int, vector<int>, greater<int>> scoville_pq;
    for (size_t i = 0; i < scoville.size(); i++)
    {
        scoville_pq.push(scoville[i]);
    }

    while(true)
    {
        // 스코빌이 가장 낮은 음식이 기준 미만이라면
        if (scoville_pq.top() < K)
        {
            // 남은 음식이 단 하나 뿐이면
            if (scoville_pq.size() == 1)
            {
                // 모든 음식을 섞었으나 스코빌 지수를 K 이상으로 만들 수 없기에
                answer = -1;
                break;
            }

            // 혼합 횟수 + 1
            answer++;

            // 섞을 두 음식의 스코빌을 변수에 할당하고 큐에서 제거
            int food1 = scoville_pq.top();
            scoville_pq.pop();
            int food2 = scoville_pq.top();
            scoville_pq.pop();

            // 섞어서 스코빌을 높인 후 결과값을 큐에 추가
            int mixture_scoville = food1 + food2 * 2;
            scoville_pq.push(mixture_scoville);
        }
        // 스코빌이 가장 낮은 음식이 기준 이상이면,
        // 나머지 음식도 자동으로 더 높아지니 더 혼합할 필요가 없음
        else
            break;
    }
    return answer;
}