[Programmers] 더 맵게

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

프로그래머스

 

문제의 조건을 읽어봅시다.

 

1. 음식들의 스코빌 지수가 주어집니다.

2. 스코빌 지수가 제일 낮은 두 음식을 섞어서 스코빌 지수가 더 높은 음식 하나를 만들어 낼 수 있습니다.

3. 문제에서는 모든 음식의 스코빌 지수가 K 이상이 될려면 최소 몇 번 음식을 섞어야 하는지를 물어봅니다.

 

과거 2021년 7월, 제가 입대하기 전에 풀었던 문제입니다. 그냥 필 받아서 다시 풀어보는데... 의외로 PS 지식 하나도 없었는데도 정상적으로 풀었습니다;;; 일단 이 문제를 풀기 위해서 우리는 어떤 기능들이 필요하냐면...

 

1. 현재 음식들 중에서 스코빌 지수가 가장 낮은 걸 빠르게 찾을 수 있어야 합니다. (Pop)

2. 두 음식이 섞인 새로운 음식을 넣은 후에도 스코빌 지수가 가장 낮은걸 빠르게 찾을 수 있어야 합니다. (Push)

 

이 두 가지 기능들을 지원하는 자료구조나 알고리즘이 필요합니다. 이 두 가지 기능은 사실 Priority Queue로 O(logN)만에 해결이 가능합니다. 그래서 예전에 저는 Priority Queue를 파이썬에서 heapq 라이브러리 가져다가 풀었습니다.

 

그런데 이번에도 이렇게 풀면 재미없으니, 저는 이번에는 multiset으로 풀었습니다. multiset도 값을 넣는 것도 O(logN) 지우는 것도 O(logN)만에 지원이 됩니다. 다만 차이는, Priority Queue가 아마도 상수 시간이 덜 드는 걸로 알고 있습니다. 그래도 multiset은 lower_bound, upper_bound가 지원이 됩니다!

 

아래는 multiset으로 푼 제 코드입니다. 음식은 최대 N-1번 섞을 수 있고, 섞을 때마다 O(logN)의 시간이 필요하므로 총 시간복잡도는 O(NlogN)이 됩니다.

 

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int solution(vector<int> scoville, int K) {
    multiset<ll> ms;
    for(auto itr : scoville) ms.insert(itr);
    ll answer = 0;
    while(ms.size() > 1){
        ll val = *(ms.begin());
        if(val >= K) break;
        
        ll new_food = 0;
        auto itr = ms.begin();
        new_food += *itr;
        ms.erase(itr);
        itr = ms.begin();
        new_food += 2 * (*itr);
        ms.erase(itr);
        ++answer;
        ms.insert(new_food);
    }
    if(*(ms.begin()) < K) answer = -1;
    return answer;
}