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

문제

프로그래머스 2019 KAKAO BLIND RECRUITMENT - 무지의 먹방 라이브 (Level 4)

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

 

---

문제 풀이

접근 방식

이 문제는 2019 카카오 블라인드 채용 1차 코딩테스트 4번 문제로,

K초에 먹어야하는 음식의 번호를 구하는 문제였다.

 

이 문제는 효율성 테스트가 있는 문제여서 시간 복잡도를 고려하여 문제를 풀어야했다.

효율성 테스트의 제한 사항을 보면 food_times의 원소가 100,000,000 이하이기 때문에,

1초씩 증가시키며 확인하는 시뮬레이션 방법을 쓰면 통과할 수가 없다.

 

우선, 각 음식은 필요 시간만큼 음식을 섭취하면 다 먹은 것으로 취급한다.

그래서 필요 시간이 작은 음식들이 먼저 없어지기 때문에, 필요 시간이 작은 순으로 정렬해주었다.

이 때, 음식 번호와 필요 시간 정보가 모두 필요하기 때문에 이 두 값을 pair 값으로 갖는 벡터를 만들어주었고,

cmp 함수를 만들어서 필요 시간이 작은 순으로 정렬해주었다.

 

그 후, (남은 음식의 개수) * (최소 필요 시간)만큼을 K에서 빼주며 탐색해야 할 시간을 감소시켜주었다.

위의 방법으로 다 먹은 음식들을 계속 지우다가 지워야할 값이 K와 같거나 큰 경우,남은 음식들을 음식 번호가 작은 순으로 정렬하여 K초에 먹어야하는 음식의 번호를 구해주었다.(0초부터 먹기 시작하므로 처음에 K에 1을 더하고 시작하였다.)

 

---

풀이 코드 - C++

#include <vector>
#include <algorithm>

using namespace std;

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

int solution(vector<int> food_times, long long k) {
    int len = food_times.size();
    long long total = 0;
    vector<pair<int, int>> idx_time;
    for(int i = 0; i < len; i++) {
        idx_time.push_back({i+1, food_times[i]});
        total += food_times[i];
    }
    if(total <= k) return -1;

    k++;
    sort(idx_time.begin(), idx_time.end(), cmp);
    int now_len = len, idx = 0, MIN = 0;
    while(1) {
        if(k > (long long) now_len * (idx_time[idx].second - MIN)){
            k -= (long long) now_len * (idx_time[idx].second - MIN);
            MIN = idx_time[idx].second;
            while(1) {
                idx++; now_len--;
                if(idx_time[idx].second != MIN)
                    break;
            }
        } else {
            vector<int> temp;
            for(int i = idx; i < len; i++){
                temp.push_back(idx_time[i].first);
            }
            sort(temp.begin(), temp.end());
            return temp[(k - 1) % now_len];
        }
    }
}

실행 결과

실행 결과 : 100.0