[프로그래머스 - 무지의 먹방 라이브] Lv.4 c++

단순 구현은 쉬우나, 효율성 때문에 오래 걸린 문제.   

 

무작정 k에 대해서 돌며 index를 구하면 터지게 되어 있음. k의 최대가 2*10^13  

 

k초에 네트워크 에러가 나고, 그 뒤에 무엇을 먹어야 하는지 구해야 한다. 결국 간단하게는 `k+1 초에 몇 번 째 음식을 먹는지` 구하는 문제다.  

 

 

위 그림처럼 표로 정리해보면, food_item[idx] 값 만 큼만 column 이 채워지는 것을 볼 수 있다.   

 

item의 모든 합보다 k+1 이 더 크다면, 이때는 먹을 음식이 이미 고갈 된 것이므로 -1을 리턴하는 것으로 먼저 전처리를 해주었다.   

 

while 문을 돌며 하나의 row씩 보면, 해당 row에 들어가는 k의 범위를 구하는 방식으로 접근했다.   

 

일단 sorted에서 가장 작은 수 * len(food_items) 만큼의 k는 full row로 채워진다. (그림의 첫번째 행과 두번째 행)   

 

다른 경우

row = 4 ) 

row 값 이상인 item column에만 채워지므로, 4 4 7 에만 k값들이 채워진다.   

 

이때, 매번 row보다 크거나 같은 값을 배열에서 찾을 필요 없이, 처음 idx 변수를 두고 while문 안에서 증가시켜주는 식으로 시간 복잡도를 최대한 줄여야 한다.

 

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

using namespace std;

vector <pair<int,int>> sorted;
long long total;

void set_sorted(int len, vector<int> food_times) {
    for (int i=0; i<len; i++) {
        total += food_times[i];
        sorted.push_back({food_times[i], i+1});
    }
    sort(sorted.begin(), sorted.end());
}

int solution(vector<int> food_times, long long k) {
    long long len = food_times.size();
    set_sorted(len, food_times);
    k += 1;
    if (k > total) return -1;
    
    long long val = sorted[0].first * len;
    if (k>=1 && k<=val) {
        int ret = k % len;
        return ret == 0 ? len : ret;
    }
    
    int row = sorted[0].first + 1;
    long long idx = 0;
    while (1) {
        while (sorted[idx].first < row) {
            idx++;
        }
        long long diff = len - idx;
        long long left = val + 1;
        long long right = val + diff;
        if (k <= right && k >= left) {
            vector <int> v;
            for (int i=idx; i<len; i++) {
                v.push_back(sorted[i].second);
            }
            sort(v.begin(), v.end());
            return v[k - left];
        }
        row++;
        val = val + diff;
    }
    return 0;
}

 

채점 결과