[C++로 풀이] 무지의 먹방 라이브 ⭐⭐⭐⭐

Date: 2021.04.13 Updated: 2021.04.13

카테고리: Programmers

📌 무지의 먹방 라이브

난이도 ⭐⭐⭐⭐

🚀 문제

입력 크기가 매우 크고(k의 최대값이 무려 20조..!) 효율성 테스트가 있기 때문에 food_times을 k번 만큼 ‘순환적으로’ 순회하면서 1 씩 감소시켜서 답을 구하면 안된다. (즉, O(k)이면 안됨) 정확성 테스트는 통과할 수 있겠지만 효율성 테스트는 절대 통과할 수 없다. 따라서 k번 순회하지 않고 답을 도출할 수 있는 효율적인 방법을 생각해야 한다.

🚀 내 풀이

예시 [4, 2, 2, 2, 15, 4], K = 16

위 예시에서 음식은 모두 6 개이다. 순서대로 차례 차례 먹다보면 가장 빨리 다 먹게 되는 음식은 2, 3, 4 번 음식이다. 왜냐하면 음식을 다 먹는데 필요한 시간이 가장 작은 시간은 2 이기 때문이다. 2, 3, 4 번 음식은 가장 적은 시간인 2 시간이 걸리기에 가장 일찍 다 먹게 될 것이다. 즉, 2 * 6 = 12 번만큼 순회를 마쳐야지만 처음으로 빈 접시가 등장한다는 것이다! 굳이 12 번 일일이 순회하지 않더라도 현재의 상태에서 가장 적은 시간이 필요한 음식의 시간(= 2)과 현재의 상태에서 남아있는 음식의 개수(= 6)를 알면 바로 2 * 6 = 12 초의 시간동안 음식을 다 비운 접시들을 알아낼 수 있다는 것이다. 답은 k시간까지 먹방을 마친 후 아직 남아있는 음식을 먹어야하므로 이렇게 k시간내에 다 먹을 수 있는 시간(음식)들, 다 먹지 못하는 시간들의 정보가 필요하다.

현재 상태에서 가장 빨리 다 먹을 수 있는 음식(시간)을 알 수 있어야 하므로 시간을 기준으로 정렬 된 정보가 필요하다.

시간의 ‘종류’를 정렬한 것은 2, 4, 15 그리고 k = 16 이라고 가정.
- 시작 상태 [4, 2, 2, 2, 15, 4]
  - 가장 빨리 다 먹을 수 있는 음식의 시간 : 2 초
  - 남아 있는 음식의 개수 : 6 개
- 2 * 6 = 12 초 후 👉 [2, 0, 0, 0, 13, 2] 가 된다는 것을 알 수 있다.
  - 가장 빨리 다 먹을 수 있는 음식의 시간 : 2 (= 4 - 2)초
    - 그 다음으로 빨리 먹을 수 있는 시간은 사실 정렬 순서 상 4 초이다. 12 초가 지났으므로 4 초짜리 음식들은 그동안 총 2 번 먹었을 것이므로 (4 - 2 = 2) 초가 남아있게 된다.
    - 가장 빨리 다 먹을 수 있는 음식의 시간을 업데이트 할 때 이전에 다 먹은 시간인 ‘2 초’ 정보가 필요하다.(4 초는 앞선 2초로 인하여 4-2 = 2 초 상태로 깎여야 하기 때문) 바로 이전에 다먹은 시간 정보도 필요하다.
  - 남아 있는 음식의 개수 : 3 (= 6 - 3) 개
    - 2 초는 총 3 개 있으므로 12 초가 지나면 2 초짜리 음식들은 다 0 이 된 상태. 따라서 6 에서 3 을 빼면 그게 바로 아직 다 안먹은 음식의 수.
- 2 * 3 = 6 초 후 👉 [0, 0, 0, 0, 11, 0] 가 된다는 것을 알 수 있다.
  - 그러니 12 + 6 = 18 초 후엔 [0, 0, 0, 0, 11, 0] 가 된다는 뜻이다! 그러나 k는 16 이라 18을 넘지 않기 때문에 이렇게 되기도 전에 답이 있다.
- 결론적으로 [2, 0, 0, 0, 13, 2] 가 [0, 0, 0, 0, 11, 0] 로 되기 전의 순회 과정에 답이 있다는 의미이다!
  - 4 초짜리 음식을 전부 다 먹으면 16초를 넘는 18 초이기 때문에 4 초짜리 음식을 전부 다 먹지는 못한다는 것을 알게 되었다. 따라서 이제부턴 4 초짜리 음식이 제거될 수 있는 시작 시간인 12 초(2초 짜리 음식들이 전부 소비 완료된 시간) 이후부터 16 초가 될 때 까지, 즉 16 - 12 = 4 초동안 “4 초 이상”의 음식들 중에서만! 순회를 하여 인덱스를 찾아내면 된다. 즉, 12 초지점에서 4 초 미만의 음식이 있는 칸은 제외하고 4 칸을 더 가면 되는 것이다.(물론 범위를 벗어나면 맨 앞으로 순환)

아무튼 위와 같은 식으로 생각하며 코드를 짰다.. 그리고 이 문제는 입력 크기가 매우 큰데다 곱하기, 더하기 연산을 하기 때문에 이와 관련된 변수들의 자료형들을 long long 으로 선언해주어야 오버플로우가 없을 것이다.

🔥 첫 번째 풀이 (시간 초과⏰)

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

using namespace std;

int solution(vector<int> food_times, long long k) {
    int answer = 0;
    int n = food_times.size(); // 접시의 총 개수
    map<int, int> freq; // key : 음식 먹는데 필요한 시간  value : 등장 횟수
    set<int> kind; // 음식 먹는데 필요한 시간 오름차순 정렬 (중복 없음) 
    for (int i = 0; i < n; ++i) {
        freq[food_times[i]]++;
        kind.insert(food_times[i]);
    }

    // 모든 시간(원소)의 합이 k 이하면 k 시간 내에 모든 음식을 다 먹을 수 있다는 것이므로 이땐 -1 을 리턴하고 일찍 끝냄
    long long sum = 0;
    for (int i = 0; i < n; ++i)
        sum += food_times[i];
    if (sum <= k) return -1;

    sum = 0; // 현재까지 전체 시간의 합
    long long temp_n = n; // temp_n : 현재 상태에서 남은 음식 개수 (n 에서 시작)
    long long now, prev = 0; // now : 현재 상태에서 가장 먼저 다 먹을 수 있는 음식(시간), prev : 바로 이전 상태에서 다 먹은 음식(시간)
    for (auto& d : kind) {  // kind 는 시간(음식)의 종류를 시간별로 오름차순 정렬한 set 
        now = d;
        long long temp = (now - prev) * temp_n; // temp : prev 음식을 비운 이후, now 음식을 다 비우는데 걸린 시간
        if (sum + temp > k) // sum + temp : 현재까지의 전체 방송 시간. k 를 넘는다면 그 전에 답이 있다는 이야기다. 따라서 빠져나온다. 이렇게 k 를 넘어버릴 수도 있으니 sum을 업데이트 하는 sum += temp 하지 않고 sum + temp 정도로만 비교하는 것
            break;
        sum += temp;  // 이제 sum 전체 시간 제대로 업뎃
        temp_n -= freq[d]; // d 음식을 다 먹었기 때문에 현재 남아있는 음식의 개수는 d 음식(시간)의 개수를 빼주면된다.
        prev = now; // 이전 음식를 지금 음식으로 업데이트
    }

    // 위에서 마지막으로 구한 sum과 now로 답을 찾는다.
    // sum + temp > k 로 빠져나왔기 때문에, 즉 이전 음식들과 다르게 고정된 k 값으로 인하여 이번 now 이상의 시간이 걸리는 음식부터 전부 다 비우는 것이 불가능해진다는 것을 위에서 알게 되었기 때문에
    // "now 이상의 시간을 가진 음식들을 원래 food_times 순서로 순회하며 k 시간이 될 때까지 먹는다"
    long long offset = (k + 1) - sum; // sum 은 now 음식이 제거될 수 있는 시작 시간 (= prev 음식이 전부 제거 완료된 시간) k + 1 시간부터 음식을 다시 먹을 수 있기 때문에 k + 1 - sum, 즉 이제 sum 시간에서부터 offset 시간만 더 진행된 곳이 답이 된다.
    long long count = 0; // count 가 offset 과 같아지면 종료시킬 것 
    int i = 0;
    for (int i = 0; ; ++i) {
        if (i == n) i = 0; // 순환
        if (food_times[i] < now) continue; // now 미만 음식은 이미 sum 초 전에 소비 완료 다 했기 때문에 지나감 (sum 초를 넘은 시점에선 빈 접시다)
        count++;
        if (count == offset) {
            answer = i + 1; // 0,1,2 를 1,2,3 번 접시로 칭하기 때문에 
            break;
        }
    }
    return answer;
}

시간 초과가 발생한 이유는 offset 만큼 food_times을 순회했기 때문이라고 판단했다. (즉 O(offset)) offset이 아주아주 큰 값일 수도 있으므로 그냥 food_times만 O(N)으로 도는게 아니라, food_times[i] < now 한 원소들까지 포함하여 순환 순회하기 때문에 food_times 전체를 여러번 돌게 될 수도 있다. 따라서 두 번째 풀이로 코드를 좀 고쳐준 후 통과하였다.

🔥 두 번째 풀이 ⭕

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

using namespace std;

int solution(vector<int> food_times, long long k) {
    int answer = 0;
    int n = food_times.size();
    map<int, int> freq;
    set<int> kind;
    for (int i = 0; i < n; ++i) {
        freq[food_times[i]]++;
        kind.insert(food_times[i]);
    }

    long long sum = 0;
    long long temp_n = n;
    long long now, prev = 0;
    for (auto& d : kind) {
        now = d;
        long long temp = (now - prev) * temp_n;
        if (sum + temp > k)
            break;
        sum += temp;
        temp_n -= freq[d];
        prev = now;
    }
    // temp_n 남아있는 음식이 없다면 -1 리턴 
    if (temp_n == 0) return -1;
    
    long long offset = k - sum;
    vector<pair<int, int>> notzero; // first : 시간  second : 번호 
    for (int i = 0; i < n; ++i)
        if (food_times[i] >= now) // now 이상인 음식들만 notzero 에 저장 (sum 시간까지 다 못 먹고 남은 음식들) 
            notzero.push_back({ food_times[i], i + 1 });
    int index = offset % notzero.size();
    answer = notzero[index].second; 

    return answer;
}

첫 번째 풀이처럼 now 미만의 음식들까지 순회하지 않고, sum 초 시간까지는 다 먹지 못하는 음식들만 모은 now 이상의 시간을 가진 음식들만 notzero 벡터에 모으고 (pair로 원래 순서도 같이 저장) offset을 이 사이즈로 나눈 나머지 값을 위치로 하는 notzero 원소의 원래 위치를 답으로 도출하였다. offset이 엄청나게 크다면 food_times 전체를 여러번 순회할 수도 있기 때문이다. 어차피 offset은 now 미만의 음식들만 카운트하는데 유효하기 때문에 now 이상인 음식들은 스킵한 notzero 에서만 카운트 하게 했다. 근데 offset이 아주 크다면 여러번 돌 수도 있으므로 notzero 사이즈로 나눈 나머지를 notzero인덱스로 구한다. 이 notzero 원소에 저장된 원래 순서(번호)가 답이 된다.

O(offset) 을 O(n) 으로 줄인 셈이다.

🔥 세 번째 풀이 ⭕

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

using namespace std;

bool comp(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}

int solution(vector<int> food_times, long long k) {
    int answer = 0;
    vector<pair<int, int>> foods; // first : 해당 음식 먹는데 필요한 시간, second : 번호 (정렬 전 원래 순서)
    int n = food_times.size();
    for (int i = 0; i < n; ++i)
        foods.push_back(make_pair(food_times[i], i + 1));
    sort(foods.begin(), foods.end()); // ⭐ "시간" 기준으로 오름차순 정렬
    int pretime = 0; // 이전에 다 먹을 수 있는 시간(음식)
    for (vector<pair<int, int>>::iterator it = foods.begin(); it != foods.end(); ++it, --n) {  // 시간 순으로 정렬된 foods 순회 O(n)
        long long spend = (long long)(it->first - pretime) * n; // it 이 가리키는 음식을 다먹는데 걸리는 시간(이전 음식 이후)
        if (spend == 0) continue; // 이미 다 먹은 음식이므로 스킵 (이미 다 먹은 동일한 시간 음식)
        if (spend <= k) {  // k 에 아직 도달하지 못했다면 반복. 
            k -= spend; // k 는 방송 정지까지 남은 시간 
            pretime = it->first; 
        }
        else { // spend > k
            k = k % n; // 이 과정 중요! 나머지로 하지 않고 그냥 k 만큼 전부 돌아버리면 시간 초과날 것이다. 내 첫 번쨰 풀이처럼
            // ⭐"번호(정렬 전 원래 순서)" 기준으로 오름차순 정렬.
            // it 반복자 원소부터!!! 정렬한다. 즉, [it ~ 마지막원소] 범위만 정렬한다.
            sort(it, foods.end(), comp); 
            return (it + k)->second; // it 이 가리키는 음식부터 다 먹을 수 없는 것이기 때문에 it 이 가리키는 음식에서 원래 순서에서 k 칸을 더 가면 답!  
        }
    }
    return -1;
}

카카오 공채 문제 풀 때마다 도움 받고 있는 유튜브.. ㅠ ㅜ 더 좋은 풀이가 있을까 해서 참고하였다. 내 풀이 로직과 거의 비슷하지만 더 짧고 깔끔한 풀이다! 난 map과 set 둘 다 사용하였는데 이 풀이에선 사용하지 않는다.

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️