프로그래머스 Level 4 무지의먹방라이브

무지의먹방라이브 (프로그래머스 Level 4)

https://school.programmers.co.kr/learn/courses/30/lessons/42891

까다로운 문제였다
처음에는 단순 queue를 사용하여 하나씩 빼주는 방식을 사용하였으나
시간초과가 발생하였다
그렇기에 로직을 수정하여 ‘우선순위 큐’를 2번 사용하는 방식으로 수정하여 문제를 해결하였다

풀이의 요점은

1. 전체값의 합이 k보다 작거나 같다면,
   장애 타이밍 전에 모든 음식을 먹었으므로 -1
   
2. fool 벡터의 최솟값 * 벡터 사이즈 가 k보다 작다면
   별도의 요소를 제거할 필요가 없으므로
   k % fSize + 1 을 return
   
3. 이후 해당 값을 이용하여
   ‘남은 용량’이 적은 순으로 ‘우선순위 큐’를 생성하여
   벡터 내의 ‘최솟값’을 갱신하여 다시 재적용
   ( checkM = (long long)(minV - prevM) * q.size())
   k가 해당 수치보다 작다면
   현재 요소 중 하나이다
   그렇지 않다면 해당 수치만큼 k에서 빼주고
   다음 큐로
   
4. k가 checkM보다 작을 때,
   ‘원래’ 순서가 다시 필요하므로
   원래 순서를 기준으로 우선순위 큐를 재조정
   이후, k % q.size() 만큼 새로운 우선순위 큐에서 빼준후
   남은 큐의 top에서 순서를 획득
   

꽤나 어려웠던 문제였기에 예시를 하나 들려고 한다
{4,2,3,6,7,1,5,8} , 27 인 경우 정답은 5가 되는데
먼저 1이 최솟값이므로
checkM 은 (1 - 0) * 8(큐 크기) = 8이 되고
이를 k에서 빼준다
k : 27 - 8 = 19

이후 원래 1이였던 요소가 ‘제거’ 되므로
큐 사이즈가 7이 되며
다시 k를 빼간다
k : 19 - 7 …
k : 12 - 6 …
k : 6 - 5 …
이 때까지 4까지 제거되고 k는 1이된다
현재 남은 수들은
{0,0,0,2,3,0,1,4}이며
이중 2인 4번째(정답은 +1 하여 5)가 되어야 한다

개인적으로 고민된 것이
우선순위 큐에서 ‘최솟값’을 빼기에 ‘마지막 순간’에
자동적으로 1,2,3,4 로 정렬되어 있는 것을
다시 원래 순서인 2,3,1,4 순으로 바꿔주어야 했던 점이며
이를 위하여 ‘우선순위 큐’를 하나 다시 파서
해당 큐에 집어넣은 후 빼주는 방식을 사용하였다

큐를 사용하면 되겠다는 대략적인 생각은 있었고
k를 저렇게 구하면 되겠다는 생각은 있었으나
시간 초과 후, 추가적으로 ‘우선순위 큐’를 생각했던 것 같다
어찌어찌 열심히 풀기는 하였지만, 실제로 이러한 문제가 주어졌을 때
짧은 시간 내에 풀 수 있을지는 자신이 없다

Code

#include <vector>
#include<queue>
#include<algorithm>

using namespace std;

int solution(vector<int> food_times, long long k) {
    long long answer = -1;
    long long minV = food_times[0];
    long long sumV = 0;
    const int fSize = food_times.size();

    for (int f : food_times)
    {
        sumV += f;
        if (f < minV)
            minV = f;
    }

    long long checkM = minV * fSize;

    if (sumV <= k)
    {
        return -1;
    }

    if (checkM >= k)
    {
        answer = (k % fSize) + 1;
        return answer;
    }

    k -= checkM;

    struct cmp {
        bool operator()(const pair<long long, long long>& a, const pair<long long, long long>& b) {
            if (a.second == b.second)
                return a.first > b.first;

            return a.second > b.second;
        }
    };

    priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, cmp > q;
    for (int i = 0; i < fSize; i++)
    {
        if (food_times[i] - minV <= 0)
            continue;

        q.push({ i + 1,food_times[i] - minV });
    }

    minV = 0;
    while (q.empty() == false)
    {
        auto p = q.top();
        int prevM = minV;
        minV = p.second;
        checkM = (long long)(minV - prevM) * q.size(); // 이전과 값이 같았다면 여기서 0 나오므로 일단 중복은 상관 x
        if (k < checkM)
        {
            int idx = k % q.size();

            // 이 시점에서 first 기준으로 다시 정렬이 필요함
            priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;

            while (q.empty() == false)
            {
                pq.push(q.top());
                q.pop();
            }

            while (idx > 0)
            {
                pq.pop();
                idx--;
            }

            answer = pq.top().first;

            return answer;
        }
        else
        {
            k -= checkM;
        }

        q.pop();

    }

    return answer;
}