[프로그래머스] 무지의 먹방 라이브

프로그래머스의 무지의 먹방 라이브 문제 풀이에 대한 포스트입니다.

문제 설명

첫 번째 풀이 (오답)

문제에서 food_times 가 { 4, 2, 3, 6, 7, 1, 5, 8 }, k 가 27 로 주어졌을 때,
food_times 에 저장된 시간을 기둥으로 그려 표시하면 아래 그림과 같이 그릴 수 있습니다.
아래 괄호는 (원소 값, 인덱스)를 표시합니다.

여기서 음식을 빠르게 먹는 순서로 오름차순 정렬하여면 다음과 같습니다.

위 그림에서 1회차를 완료할 경우 가장 아래 행이 제거되고 모든 음식의 소요시간 값이 1씩 감소합니다.
이때, 첫 번째 음식인 (1, 6) 음식은 제거됩니다.
2회차에서는 2행이, 3회차에서는 3행이 실행되어 k 회차까지 진행하고자 하였습니다.

int solution(vector<int> food_times, long long k) {
    k += 1;
    if(k <= food_times.size())
    {
        return k;
    }
    
    priority_queue<pair<int, int>> pq;
    
    for(int i = 1; i <= (int)food_times.size(); ++i)
    {
        pq.push(make_pair(-food_times[i - 1], -i));
    }
    
    int answer = -1, prev = 0;
    int len = (int)food_times.size();
    
    while(pq.empty() == false)
    {
        auto curr = pq.top();
        pq.pop();
        
        if(-curr.first == prev) 
        {
            len -= 1;
            continue;
        }
        
        if(k <= ((-curr.first - prev) * len))
        {
            answer = -curr.second;
            break;
        }
        
        k -= ((-curr.first - prev) * len);
        prev = -curr.first;
        len -= 1;
    }
    
    return answer;
}

그러나 위의 코드는 정상적으로 동작하지 않았습니다.
문제는 최대힙을 사용한 우선순위 큐로 삽입, 삭제 시간을 줄였지만

효율성 테스트 제한사항을 보면 food_times 의 최대 길이는 200,000 이고 각 원소는 1억 이하이며
무지가 음식을 먹는 횟수는 최대 20조(2 x 10^13) 입니다.
만약, 20조 번 만큼 음식을 먹을 때 우선순위 큐를 사용하더라도 시간 초과가 발생합니다.
따라서 \(O(k) = O(20,000,000,000,000)\) 이므로 순차 탐색보다 더 빠른 알고리즘을 고려해야 합니다.

두 번째 풀이

우선순위 큐는 삽입과 삭제가 매우 빠르고 최대힙일 경우 최댓값, 최소힙을 때는 최솟값이
\(O(1)\) 의 시간 복잡도로 동작합니다.
그러나 이 문제에서는 중간에 원소가 추가되는 일이 없어 오히려 손해라고 판단했습니다.
따라서 vector 와 sort 함수를 사용해서 오름차순으로 정렬하도록 수정하였습니다.
정렬된 모습은 위 그림과 동일합니다.

이전 코드와 달리 두 번째 시도에서는 결과를 출력하기 직전 원소를
Comp 함수의 내용처럼 .second 원소를 기준으로 재정렬 했습니다.
이때, 남은 음식 중 작아진 k 값은 정답을 가르키고 있습니다.

bool Comp(const pair<int, int>& lhs, const pair<int, int>& rhs) {
    return lhs.second < rhs.second;
}

int solution(vector<int> food_times, long long k) {

    vector<pair<int, int>> food;
    int len = food_times.size();
    for(int i = 0; i < len; ++i)
    {
        food.push_back(make_pair(food_times[i], i + 1));
    }
    
    sort(food.begin(), food.end());
    
    int prev = 0;
    for(vector<pair<int, int>>::iterator it = food.begin(); it != food.end(); --len, ++it)
    {   
        // (테이블 회전 횟수) == (현재 음식 시간 - 이전 음식 시간)
        long long spend = (long long)(it->first - prev) * len;

        // 음식 시간이 중복인 경우 
        if(spend == 0) continue;
        
        // 한 바퀴 완전 회전
        if(spend <= k)
        {
            k -= spend;
            prev = it->first;
        }
        // 한 바퀴를 못 돌고 이번에 멈춤
        else
        {
            k = k % len;
            sort(it, food.end(), Comp);
            return (it + k)->second;
        }
    }
    
    return -1;
}

참고

공부하는 식빵맘님 블로그
얍문님 블로그