[ 프로그래머스 무지의 먹방 라이브 (Lv4) ] (C++)

프로그래머스의 무지의 먹방 라이브(Lv4) 문제이다.

[ 문제풀이 ]

효율성 테스트가 있는 문제이고, 본인은 효율성 테스트를 전혀 통과하지 못하는 상태였다. 그래서 여러 검색을 많이 해봤는데, 정말 말도 안되는 풀이방법에 대해서 알게 되었고 그 풀이법으로 결국 효율성 테스트를 통과하게 된 문제이다.

지금부터 본인이 알게된 방법으로 문제를 해결하는 과정을 알아보자.

먼저, 이 문제의 가장 큰 골칫덩어리는 효율성 테스트이다. 문제에 주어진 효율성 테스트 제한 사항만 보더라도 숫자가 딱봐도 굉장히 큰 숫자들로 이루어져있고, 단순하게 풀어서는 효율적이지 못하다 라는 결과를 받을게 뻔하다.

지금부터 하나의 예를 들어서 풀이 과정을 알아보자.

음식을 먹는데 드는 필요한 시간이 { 3, 1, 6, 5, 10, 9, 5  } 이렇게 주어졌고, K = 25 라고 가정해보자.

먼저 위의 음식을 먹는데 드는 필요한 시간을 그림으로 표현해보면 다음과 같이 나타낼 수 있다.

.

위의 그림에서 칸안에 적혀있는 숫자는 '음식을 먹는 시간' 이다.

즉, 1번 음식은 1초, 8초, 14초에 먹게되고, 2번 음식은 2초에 먹게 되고, 3번 음식은 3, 9, 15... 초에 먹게 된다는 것을 의미한다.

K =25 라고 했을 때, 25초까지 음식을 먹고, 그 다음 음식을 먹게 되므로, 결과적으로 4번 음식을 먹게 된다.

그럼, 위와 같이 음식을 하나하나씩 없애는 것이 아니라, "양이 가장 적은 음식부터 완전히 없애는 방식" 을 이용해서 계산을 해보자. 그러기 위해서, 먼저 위의 음식을 시간순으로 정렬시켜보자.

.

그럼 위와 같은 형태로 표현할 수 있다. 그럼 가장 아랫줄을 한번 보자. 가장 아랫줄을 처리하게 되면, 자연스럽게 2번 음식은 더 이상 남은 음식이 없기 때문에, "완전히 없애버릴 수 있게된다".

.

위와 같이 동그라미 친 부분에 있는 음식을 모두 다 먹는다고 가정해보자. 그럼 몇 초가 걸릴까 ?? 7초가 걸리게 된다.

7개의 음식을 먹는 상황이기 때문에, 총 7초의 시간이 걸리게 된다.

그럼 K = 25 에서, 가장 아랫줄을 다 먹음으로써 2번 음식을 완전히 없애버릴 수 있고, 그에 따라서 K = 18초가 남게 된다.

그럼 그 다음줄을 한번 보자. 1번 음식이 있다. 1번 음식은 아직 2초 만큼의 음식이 더 남아있다.

즉 ! 이런 경우에는 첫 번째 상황처럼 '한 줄'이 아닌 2줄을 먹어야 1번 음식을 완전히 끝내버릴 수 있다.
.

다시 이야기해서, 위의 그림에서 동그라미친 줄만 없애버린다면, 1번 음식이 '검은색 점'으로 표시된 양 만큼 남아있게 된다.

즉 ! 우리가 하고자 하는 "양이 가장 적은음식부터 완전히 없애려고 한다!" 에 부합하지 않게 된다는 것이다.

그럼 1번 음식을 완전히 없애려면 ??? 우리는 다음과 같이 2줄을 한번에 계산해 줘버리면 1번 음식을 없애버릴 수 있다.

.

이렇게 2줄을 한번에 없애버리면 ? 1번 음식을 완전히 다 먹은 걸로 처리가 가능하다.

그럼 저 2줄을 처리하는데는 몇초의 시간이 걸리게 될까 ?? 바로 12초이다. 왜 ?? 6개의 음식을 2번씩 먹는 경우로 생각할 수가 있다. 즉 ! 12초가 걸리게 된다.

그럼, 위의 2줄을 한번에 처리함으로써 우리는 1번 음식을 완전히 끝내버릴 수 있고, 그에 따라 12초의 시간이 소요된다.

가장 처음에 2번 음식을 처리하는데 7초가 걸렸으므로 K = 25에서 K = 18초가 남아있는 상태이고, 이번에 계산한 1번 음식을 처리하기 위해서 12초를 써버렸으니 K = 18 - 12 = 6초가 남아있게 된다.

그럼 이제 음식의 양이 가장 적은 2번, 1번 음식은 모두 처리해 주었다. 그 다음 음식을 처리해보자.

그 다음 음식은 4번 음식인데, 마찬가지로 한 줄만 계산하기에는 4번 음식을 완전히 비워버릴 수가 없다. 즉 ! 이번에도 2줄을 한번에 계산해 주어야 한다.

.

즉 ! 우리는 4번 음식을 완전히 처리하기 위해서 위에서 동그라미 쳐진 2줄을 처리할 것이다. 그렇다면 위에서 동그라미 쳐진 2줄을 처리하는데 몇 초가 걸리게 될까 ? 10초가 걸리게 된다. 칸 수를 직접 카운트 해봐도 알 수 있겠지만, 5개의 음식을 2번씩 먹는 경우가 되기 때문에 10초가 걸리게 된다.

그럼 여기서 K 값을 한번 계산해보자. 우리는 첫 번째 2번 음식을 먹는데 7초를 소모했으므로 K =25 에서 K =18이 되었고,

1번 음식을 먹는데 12초를 소모했으므로 K = 18에서 K = 6이 되었다.

그리고 이제 위의 동그라미를 계산해보면 K = 6에서 10을 빼버리면.... -4 가 되어버린다. 하지만 -4초 라는 것은 존재하지 않는다.

즉 ! 우리가 구하고자 하는 정답이 위의 동그라미 안에 있다 라는 것을 우리는 알 수 있다.

가장 단순하게 지금부터 직접 카운트를 해보더라도, 3 - 4 - 5 - 6 - 7 번 음식을 한번씩 먹는데 5초가 걸리게 되고, 3번 음식을 먹는데 6초가 걸리게 된다. 그리고 K= 0이 되므로, 방송이 끊기게 된다. 그 이후 방송을 다시 키게 되면 '4'번음식부터 먹으면 된다.

그럼 이 과정을 직접 카운트 하지 말고 조금 단순하게 구해보자.

먼저, 남은 K 시간 동안 남은 음식을 몇 싸이클을 돌 수 있는지 체크를 해보자. 현재 위의 동그라미 친 부분에는 5개의 음식이 존재하고, K = 6초이다. 즉 ! 5개의 음식을 한 싸이클 만큼은 모두 먹을 수 있게 된다. 그리고 1초가 남게 된다.

그럼 가장 앞에 있는 음식을 한 번더 먹을 수 있게 되고 그 다음 음식이 정답이 된다라는 것을 알 수 있다.

그런데 ! 여기서 생각해줘야 할 것이 위의 그림에 속으면 안된다는 것이다. 위의 그림은 내 마음대로 '음식을 먹는 시간의 순서에 따라서 오름차순으로 정렬' 되어 있는 상태이지, 위의 순서대로 음식을 먹는 것은 아니라는 것이다.

다시 말해서, 위의 빨강색 동그라미친 부분의 음식을 먹는다고 해서, 4 - 7 - 3 - 6 - 5 의 순서대로 한 번씩 다 먹은 후에, 다시 4번 음식을 먹고, K =0이 되니까 그 다음음식은 7번 음식! 이라고 하면 안된다는 것이다.

왜 ? 실제로 음식을 먹는 순서대로 먹는다면 4 - 7 - 3 - 6 - 5가 아닌, 3 - 4 - 5 - 6 - 7 의 순서대로 먹을 것이기 때문이다.

즉 ! 오름차순으로 정렬되어 있는 위의 상태를, 다시한번 "번호의 순서대로 정렬" 시켜주어야 한다.

그리고 나서는 ? "K % 남아있는 음식의 수" 가 정답이 되는 것이다. "K % 남아있는 음식의 수" 가 무엇을 의미하는 값이길래 저게 정답이 되는 것일까 ?? K % 남아있는 음식의 수를 한다라는 것은, "남은 K시간동안, 남은 음식들을 몇 싸이클을 돌 수 있는지, 그리고 더 이상 싸이클이 이뤄지지 않을 때, 몇 개의 음식을 더 먹을 수 있는지?" 를 의미한다.

위의 상황에 대입시켜보자. K = 6이고 남아있는 음식의 수 = 5 이다. 6 % 5 = 1 이 된다. 실제로, 이 값이 의미하는 것은, "남은 6초 동안은, 5개의 음식을 모두 한번씩은 먹을 수 있습니다. 그리고 나서, 1개의 음식을 더 먹을 수 있습니다" 라는 것을 의미한다.

즉, 3 - 4 - 5 - 6 - 7 의 음식을 모두 먹고, 3번 음식까지 먹을 수 있다 라는 것을 이야기한다. 그리고 나서 '4'번음식이 그 다음 먹어야 할 음식이 된다 라는 것을 이야기 하는 것이다.

위와 같은 방식으로 정답을 구할 수가 있다. 그럼 위의 설명을 토대로 실제로 구현할 때는 값들을 어떻게 구하는지 알아보자.

위의 설명을 보면, 어떤 음식을 처리할 때는, 한 줄만 곱하기도 하고, 어떤 음식을 처리할 때는 두 줄을 곱하기도 하고, 아마 어떤 경우에는 3줄을 곱하기도 할 것이다. 그리고 어느 타이밍에는 음식의 수가 7개이고, 어느 타이밍에는 5개이고, 어느 타이밍에는 6개이고.. 이런 값들을 구하는 방법을 알아보자.

지금부터의 핵심은 "우리는 하나의 음식을 완전히 없애버릴 수 있는 순서대로 계산" 했다 라는 것이다.

위의 예시를 그대로 가져와서 이용하겠다. 음식의 수 = 7개이다. 즉 ! 가장 초기에 음식을 먹기 전에, 우리가 어떠한 연산을 시작하기 전에 음식의 갯수는 7개 라는 것이다. (빠른 이해를 위해 그림을 다시 가져오겠다.)
.

그런데, 가장 처음에 2번 음식을 완전히 없애버렸다. 그럼 ? 음식의 수가 7개에서 6개가 되는 것이다.

즉 ! 음식을 한번 처리할 때 마다, 남은 음식의 수를 -- 해줘버리면 된다. 이 음식의 수를 N 이라고 가정한다면, N-- 가 진행되는 것이다.

그리고 2번 음식을 처리할 때 보면, 한 줄만 계산을 해 주었다. 그런데 그 다음 1번 음식을 처리할 때는 2줄을 한번에 계산해 주어야만 했었다. 이 '2줄' 이라는 값은 어디서 나오는 걸까 ??

.

바로 이 높이이다. 이 높이만큼 우리는 계산을 해주면 되는데, 마치 저 높이는 딱봐도, 첫 번째 '2번 음식'과 '1번 음식'의 높이 차이로 계산을 할 수 있을 것만 같다. 즉 ! 1번 음식을 모두 먹는데 걸리는 시간 = 3초, 2번 음식을 모두 먹는데 걸리는 시간 = 1초.

이 둘의 차이는 '2초'가 된다. 즉 ! 2줄을 계산해 주어야 하는 것이다.

그런데, 가장 처음에 처리한 1번 음식은 ?? 단순하게 "이전에 먹는 음식을 모두 먹는데 걸리는 시간 = 0초" 라고 설정해 주면 된다.

혹여나, 2번 음식이 모두 먹는데 걸리는 시간이 '2초'라고 하더라도, 2초 - 0초를 하게 되면 높이차이가 '2'가 되고, 이 경우에는 2줄을 계산하게 될 것이다.

즉, 우리가 처리해야 될 '줄 수' 는 "현재 완전히 없애고자 하는 음식을 먹는데 걸리는 시간 - 이전에 없앴던 음식을 먹는데 걸린 시간" 이 된다. 이렇게 '줄 수'를 알게 된다면, 해당 음식을 완전히 없애는데 걸리는 시간은 "현재 남은 음식의 수 * 줄 수" 가 된다.

위의 예시에서 2번 음식 같은 경우에는 7개의 음식이 남았었고, 줄 수가 1이였으므로 K 값이 1 * 7 만큼 감소해서 25에서 18이 되었다. 1번 음식 같은 경우에는 6개의 음식이 남았었고, 줄 수가 2였으므로, K값이 6 * 2 만큼 감소해서 18에서 6이 되었다.

여기서 또 하나의 경우를 더 생각해 봐야 한다. 우리가 위에서 예를 든 경우에는 해당하지 않는 경우였다.
.

만약, 여기서 K값이 충분히 커서, 위의 동그라미까지 모두 계산이 되었다고 가정해보자.

즉, 4번 음식을 완전히 없애기 위해서 "남은 음식의 수(5) * 줄 수(2) = 10" 만큼 K 값이 감소했다고 가정해보자.

그럼 그 다음은 ? 7번 음식이 된다. 그런데 ! 7번 음식을 계산하기 위해서 이전 음식과의 높이차이를 보니까 0이다.

둘 다 똑같이 음식을 다 먹는데 '5초'의 시간이 걸린다. 그럼 이런 경우에는 ?? 계산을 할 필요가 없다.

왜냐하면, 위의 동그라미친 부분이 계산됨으로써 4번 음식을 모두 다 먹었다고 가정해보자. 그럼 이 때, 7번 음식은 남아있을까 ??

아니다. 7번 음식 또한 자연스럽게 다 먹어졌다. 즉 ! 이전 음식과의 높이차이가 0일 때는 별다른 계산을 해주지 않고 그 다음 음식을 처리하는 것으로 넘어가 주면 된다.

그래서 본인은 가장 먼저 구조체를 선언했고 구조체 배열을 통해서 음식들을 관리해 주었다.

구조체에서는 { 음식을 먹는데 걸리는 시간 , 음식의 번호 } 를 멤버변수로 만들어서 관리해 주었다.

그리고 이 구조체배열을 '음식을 먹는데 걸리는 시간'의 순서로 정렬을 해서 위에 풀이처럼 진행해 주었다.

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
struct FOOD
{
    int Food_Time;
    int Num;
};
 
FOOD Food[200010];
 
bool Cmp(FOOD A , FOOD B)
{
    if (A.Food_Time < B.Food_Time) return true;
    return false;
}
 
bool Cmp2(FOOD A, FOOD B)
{
    if (A.Num < B.Num) return true;
    return false;
}
 
int solution(vector<int> food_times, long long k)
{
    int N = food_times.size();
    for (int i = 0; i < N; i++)
    {
        Food[i].Food_Time = food_times[i];
        Food[i].Num = i + 1;
    }
    sort(Food, Food + N, Cmp);
 
    int Prev_Time = 0;
    int Temp_N = N;
    for (int i = 0; i < N; i++ , Temp_N--)
    {
        long long Diff = (long long)(Food[i].Food_Time - Prev_Time) * Temp_N;
        if (Diff == 0) continue;
        if (Diff <= k)
        {
            k = k - Diff;
            Prev_Time = Food[i].Food_Time;
        }
        else
        {
            k = k % Temp_N;
            sort(Food + i, Food + N, Cmp2);
            return Food[i + k].Num;
        }
 
    }
    return -1;
}