[프로그래머스]2019 KAKAO BLIND RECRUITMENT : 무지의 먹방 라이브 (level 4) (c++)

programmers.co.kr/learn/courses/30/lessons/42891

코딩테스트 연습 - 무지의 먹방 라이브

 

정렬

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

struct food {
    int idx;
    ll time;
};

bool comp_by_time(food &A, food &B)
{
    return A.time < B.time;
}

bool comp_by_idx(food& A, food& B)
{
    return A.idx < B.idx;
}

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

    // {인덱스, 시간} 벡터 생성
    vector<food> food_idx_times;
    for (int i = 0; i < food_times.size(); ++i)
    {
        food_idx_times.push_back({ i + 1, food_times[i] });
    }
    
    // 시간을 기준으로 오름차순 정렬
    sort(food_idx_times.begin(), food_idx_times.end(), comp_by_time);
    int size = food_idx_times.size();

    for (int i = 0; i < size; ++i)
    {
        /*
            time_passed_per_round = (현재 최소 음식 시간 * 남은 음식 개수) 
            k = 남은 시간
                        
            이때 food_idx_times벡터는 시간 기준으로 오름차순 정렬되어있으므로
            현재 최소 음식 시간 = time[i] - time[i - 1] 이다.

            한 라운드에 현재 최소 음식 시간을 남은 각각의 음식에서 차감한다.
            k에서는 time_passed_per_round을 차감한다.
        */
        ll bf_time = (i == 0) ? 0 : food_idx_times[i - 1].time;
        ll min_time = food_idx_times[i].time - bf_time;
        ll time_passed_per_round = min_time * (size - i);

        // 남은시간이 차감될 시간보다 더 작을때
        if (time_passed_per_round > k)
        {
            // 인덱스를 기준으로 오름차순 정렬
            sort(food_idx_times.begin() + i, food_idx_times.end(), comp_by_idx);
            
            // 남은 음식 중에서 k번째 음식 인덱스값 반환
            return food_idx_times[k % (size - i) + i].idx;
        }

        k -= time_passed_per_round;
    }

    return -1;
}

 

 

TIP_문제요약

무지는 다음과 같은 방법으로 음식을 섭취한다.

- 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
- 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
- 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.
   다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.
- 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.

food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
k 는 방송이 중단된 시간을 나타낸다.

 

문제를 요약하면 다음과 같다. 

1. 무지는 총 k초동안 1초씩 모든 음식을 순서대로 돌아가면서 먹는다

2. food_time이 작은 순서대로 음식이 동난다

3. k번째로 먹을 음식을 구하라

 

 

그리고 효율성 테스트의 제약사항은 다음과 같다.

food_times 의 길이는 1 이상 200,000 이하이다.
food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다.
k는 1 이상 2 x 10^13 이하의 자연수이다.

 

food_times 모든 원소를 하나하나 1초씩 깎아가는 건 비효율적이다.

위 제약사항을 참고하면 food_times를 기준으로 알고리즘을 짜되,

시간 경과는 k를 기준으로 계산해야 한다. 

 

 

 

TIP_풀이해설

위 풀이는 한번에 최대한 여러 음식의 시간을 차감하는 전략이다. 

1 time_passed/round = 최소 음식 시간(0 제외) * 남은 음식 개수를

k가 충분히 있는 동안 차감해 나간다.

 

예를 들어 food_times = [0, 2, 5, 7],  k = 10 이라 하자

남아있는 전체 음식에서 2씩 차감한다 하면 총 2 * 3 = 6초가 지나게 된다.

그러면 k = 10 - 6 = 4초로, 아직 세부 인덱스를 계산하지 않아도 된다.

 

이제 food_times = [0, 0, 3, 5], k = 4 가 되었다.

남아있는 전체 음식에서 3씩 차감한다고 하면 3 * 2 = 6초인데

남은 k(=4초)의 크기가 더 작기 때문에, 이제 세부 인덱스의 크기를 결정해야 한다.

 

이 과정을 수기로 나타내면 다음과 같고,

시작 : food_times = [0, 0, 3, 5],  k = 4

과정 : 

food_times = [0, 0, 2, 5],  k = 3

food_times = [0, 0, 2, 4],  k = 2

food_times = [0, 0, 1, 4],  k = 1

food_times = [0, 0, 1, 3],  k = 0

여기서 다음 순서는 food_times[2]가 될 차례였다.

따라서 답은 2이다.

 

식으로 나타내면 다음과 같다.

food_idx_times[k % (size - i) + i].idx

 

 

 

TIP_최소 음식시간

먼저 food_times배열을 오름차순으로 정렬한다.  

예를 들어 food_times = [1, 2, 5, 7] 이라 하자.

그러면 1round에서 최소 음식시간은 1초가 된다.

 

그러면 2round에서는?

각 요소에서 1초씩을 깎는다면 food_times = [0, 1, 4, 6]가 되므로

2round에서 최소 음식 시간도 역시 1초가 된다. 음?

 

문제가 있다.

위 풀이는 k에서만 경과시간을 차감하므로

food_times배열은 2round에서도 여전히 [1, 2, 5, 7]인 상태이다.

 

그러면 어떻게 N round에서 그때 시점의 최소 음식시간을 구할까?

--> 직전 요소와의 차이값이다. 

매 round마다 최소 요소값 만큼 차감하고 있고, 시간을 기준으로 오름차순 정렬했기 때문이다!