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

문제 링크

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

프로그래머스

무지가 라이브 방송을 하고있다. K초 후에 네트워크 장애로 인해 방송이 중단된다. 중단 된 이후 몇 번 음식부터 먹어야하는지 무지에게 알려주자.

 

풀이

효율성 테스트에서는 k의 범위가 1부터  2 x 10^13까지 주어지기 때문에 직접 하나씩 먹어서 K초 후 몇 번을 먹는지 알아내려면 O(20조) 만큼의 시간이 걸려 시간초과를 받게된다.

직접 먹어보는 방법으로는 정확성 테스트는 통과할 지라도 효율성 테스트는 절대 통과하지 못한다.

 

나는 공부하는 식빵맘님의 블로그를 참고하며 공부했다.

 

먼저 주어진 예시를 살펴보자.

입력값 〉	[3, 1, 2], 5

1번 음식부터 차례로 먹는데 3, 1, 2초의 시간이 걸리며 네트워크 오류는 5초 후에 발생한다.

 

남아있는 음식들 중에서 가장 적은 시간이 필요한 음식을 소모할 동안은 모든 음식을 섭취할 수 있다.

즉 음식을 시간 순으로 정렬하면 [1, 2, 3] 이 되고

가장 적은 시간이 소모되는 음식의 소모기간은 1초이다. 한 바퀴 동안은 모든 음식을 섭취할 수 있다는 뜻이다.

1바퀴 * 3개(남은 음식의 수) = 3초.

3초가 지나고 나서 최소 하나의 음식이 모두 소모된다는 뜻이다.

 

우리는 직접 순회하지 않고도, 남은 음식 중 처음 음식이 없어지는 데 걸리는 시간을 알 수 있다.

이후 음식은 [0, 1, 2] 가 되고 남은 음식은 2개가 된다.

남아있던 음식에서 0이 되어버린 음식의 수만큼 빼서 남은 음식의 수를 알아낸다.

남은 음식 중 소모 기간이 가장 적은 음식의 소모기간은 1초다.

1바퀴 * 2개(남은 음식의 수) = 2초.

2초가 지나야 또 새로운 음식이 모두 소모된다.

2초 이후 남은 음식은 [0, 0, 1] 이 된다.

이때 K = 3 + 2로 5초.

 

네트워크 마비 시간인 5초가 되었고, 다음에 먹을 음식은 남은 음식들 중 첫 번째로 등장하는 음식이 답이 된다.

하지만 정렬 한 이후이기 때문에 남아있는 음식들이 기존에 몇 번째 음식이었는 지 알 수 없다.

따라서 음식을 정렬하기 전 foods 라는 새로운 pair<int,int> 벡터를 만들어서

foods -> first 에는 음식의 소모 시간을, foods -> second 에는 음식의 번호를 저장해둔다.

 

예시를 조금 더 크게 들어보자.

입력값 〉	[4, 2, 2, 2, 15, 4], 16

6개의 음식이 존재하며, 네트워크는 16초 후에 마비 된다.

 

먼저 음식들을 시간 순서대로 정렬한다 => [2, 2, 2, 4, 4, 15] 

초기 남아있는 음식의 수는 총 음식의 수와 같다 N = 6.

소진되는데 가장 적은 시간이 걸리는 음식의 소모 시간은 2초다.

회전판을 두 바퀴를 돌 동안에는 완전히 소모되는 음식이 없다는 의미이다.

2바퀴 * 6개(남은 음식) = 12초.

12초가 지나고 새롭게 완전히 소모된 음식이 나온다는 뜻이다.

2바퀴 후 모두 소진된 음식은 3개. 따라서 남은 음식은 6 - 3 = 3개

현재 회전판의 상황은 [0, 0, 0, 2, 2, 15]

소진되는데 가장 적은 시간이 걸리는 음식의 소모 시간은 2초다.

2바퀴 * 3개(남은 음식) = 6초.

또 다시 6초가 지나야 새로운 음식이 완전히 소모된다.

그런데 12초 + 6초 = 18초 > k

새로운 음식이 소모되기 전에 네트워크 오류가 발생한다는 뜻이다.

현재 시간은 12초가 지난 상태이므로 4초뒤에 오류가 발생하는 것을 알 수 있다.

남은 음식은 3개. 즉 한바퀴가 돌고도 1초가 지났을 때 오류가 발생한다.

따라서 1초가 지난 후 어떤 음식을 먹게 될지를 구하는 것과 똑같다.

 k(남은 시간) %= n(남은 음식의 수) 의 과정을 통해 순회하는 시간을 줄여준다.

남은 음식들 [ 2, 2, 15 ] 중 1초 후에 첫번째 음식을 먹게되고, 방송을 다시 켰을 때 먹어야 할 음식은 두 번째에 있는 음식이다.

 

남은 음식들을 기존의 음식 번호 순서대로 정렬해 준 후, k 번째에 있는 음식의 음식 번호를 리턴하면 된다.

 

코드 작성

#include <bits/stdc++.h>
using namespace std;
 
bool cmp(const pair<int,int>& a, const pair<int,int>& b){
    if(a.second < b.second)
        return true;
    return false;
}
 
int solution(vector<int> food_times, long long k) {
    int answer = 0;
    vector<pair<int,int>> foods;
    for(int i = 0; i<food_times.size(); i++)
        foods.push_back({food_times[i], i + 1}); //걸리는 시간, 원래 순서
    //정렬 후에도 원래 순서를 잃지 않기위해서
    
    sort(foods.begin(), foods.end());//먹는데 걸리는 시간순에 따라 정렬
 
    int n = food_times.size(); //남아있는 음식의 개수
    int pre = 0; //직전 음식을 다먹은 시간
    
    for(vector<pair<int,int>>::iterator it = foods.begin(); it != foods.end(); it++){
        long long spend = (long long)(it->first - pre) * n;
        if(spend == 0){ //이미 시간이 계산된 음식임
            n--;
            continue;
        }
        if(spend <= k){ //아직 방송이 종료되지 않음
            k -= spend;
            pre = it->first;
            n--;
        }
        else{ //방송시간 초과 => 순회를 통해 몇 번째 음식을 먹어야할지 찾아야함
            k %= n; //k가 남아있는 음식 수보다 많으면 여러번 회전해야함
            sort(it, foods.end(), cmp); //남아있는 음식을 번호순서대로 정렬
            return (it + k)->second;
        }
    }
    return -1;
}

 

한 바퀴를 도는데 걸리는 시간이, 남은 음식의 수와 같을 것이라는 생각은 했지만

나는 한 번에 한 바퀴씩 돌아서 시간초과를 받았다.

여러바퀴를 한 번에 계산하려 했지만, 만약 k를 넘게됐을 때 어떻게 처리해야할 지 몰라서 못 풀었다.

 

알고리즘을 잘하는 사람들을 보면 어떻게 이런 방법을 생각 해내는 지 신기하다.