[프로그래머스/C++] 무지의 먹방 라이브 (2019 KAKAO BLIND RECRUITMENT)

 

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

처음에 이 문제를 봤을 때, 어떻게 풀까 고민을 많이 했다.

 

고민 끝에 크기 비교와 나누기를 잘 이용하면 쉽게 풀리겠다는 생각이 들었다.

 

먼저 음식을 먹는 시간인 food_times를 정렬한다. 

여기서 음식을 먹는데 걸리는 시간이 가장 적은 음식을 다 먹기 전까지는 모든 음식의 개수가 그대로다.

 

만약 가장 시간이 적게 걸리는 음식을 다 먹었다면, 음식의 개수가 줄어든다. 

 

그림을 보면 이해가 쉽다.

음식을 먹는데 걸리는 시간이 위와 같다고 가정하자.

그러면 먹는데 걸리는 시간이 가장 적게 드는 음식은 첫번째 음식(2) 이다.

그렇기 때문에 이 회전판이 두바퀴 돌 때 까지는 음식의 길이에 영향을 미치지 않는다.

 

만약 가장 시간이 가장 적게 드는 음식을 먹었다면, 음식의 길이가 줄어들고 그 다음으로 시간이 적게 걸리는 음식을 다 먹기 전까지는 음식의 길이가 그대로다. 

길이가 줄어든 상태

 

이를 이용하면 최대 20만번의 연산만 필요하므로 정렬 시간인 O(nlog(n))으로 문제를 해결할 수 있다.

 

이렇게 음식의 길이를 구한다면, 몇 번째 음식을 먹을 차례인지는 나머지 연산으로 쉽게 계산할 수 있다.

 

예를 들어 k가 5고 음식이 위 그림과 같다고 가정하면, 가장 적게 걸리는 음식의 시간이 2 이므로,

k<=2*4(음식 길이)이다.

그러므로 위 조건에서 k 시간 사이에 음식을 먹을 경우 음식의 길이는 변동이 없다는 사실을 알고 있으므로,

k%4(음식길이)=1 이고, 내가 먹을 차례의 음식은 1번 index인 2번째 음식임을 알 수 있다.

 

여기서 음식을 먹는데 걸리는 시간이 같은 음식이 있을 수 있으므로, 음식을 먹는데 시간이 같은 음식들의 개수를 세서 계산을 편하게 했다.

 

​

[아이디어 정리]

1. 음식을 먹는데 걸리는 시간 순서대로 정렬한다.
2. 이후 먹는데 시간이 걸리는 음식을 전부 섭취할 때 까지 걸리는 시간이 k보다 큰지 작은지 비교한다. (음식의 길이가 그대로인 구간)
3. 만약 음식을 전부 섭취할 때 걸리는 시간이 k보다 크다면 음식의 길이가 변하지 않는 동안에, 방송이 중단된 시간이 끝났으므로, k%(음식의 길이)+1번째 음식을 먹을 차례다.
4. 만약 특정 음식을 전부 섭취하는데 걸리는 시간이 k시간 보다 작다면, 그 음식을 다 섭취한 상태이므로 특정 시간이 걸리는 음식들을 먹는데 걸리는 시간을 k에서 뺀다.
5. 이후 음식의 길이를 줄이고, 음식의 섭취에 걸리는 시간이 적은 음식을 다시 먹으면서 계산을 반복한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

int solution(vector<int> food_times, long long k) {
    set<int> foodSet;
    map<int,int> foodMap;
    for (int i=0; i<food_times.size(); i++)
    {
        foodSet.insert(food_times[i]);
        foodMap[food_times[i]]+=1;
    }
    vector<int> foodV(foodSet.begin(), foodSet.end());
    sort(foodV.begin(), foodV.end());
    long long nowfoods=food_times.size();
    long long prevTime=0;
    vector<int> foodSeat;
    for (int j=0; j<foodV.size(); j++)
    {
        int nowTime=foodV[j];
        long long kt=nowfoods*(nowTime-prevTime);
        if (k-kt>=0)
        {
            nowfoods-=foodMap[nowTime];
            prevTime=nowTime;
            k-=kt;
        }
        else
        {
            for (int i=0; i<food_times.size(); i++)
            {
                if (food_times[i]>=nowTime)
                {
                    foodSeat.push_back(i+1);   
                }
            }
            int tt=k%foodSeat.size();
            return foodSeat[tt];
        }
    }
    return -1;
}

 

---

 

설명은 복잡하지만 쉽게 말해 시간이 가장 적게 걸리는 음식을 빼면서, 변동된 음식의 길이를 계산한 것이다.

문제를 풀 때 까지 내가 생각한 아이디어가 맞나? 싶었는데 다행히 맞게 푼 것 같다.

프로그래머스