[카카오 코딩 테스트] 무지의 먹방 라이브

https://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/

2019 카카오 신입 공채 1차 코딩 테스트 문제 해설

4번 무지의 먹방 라이브는 효율성이 중요한 문제였습니다.

정확성만 보면 쉽게 풀 수 있는 문제 였지만, 효율성이 정답률이 5.52% 밖에 안됬습니다..ㄷㄷ

 

저도 효율성에서 자꾸 막혀서 결국 정답자 분의 코드를 보며 수정했는데요..

 

코드도 엄청 짧고 복잡하게 생각할 필요가 없는 문제였습니다..

 

처음에는

1. 시간을 기준으로 오름차순으로 정렬 

--- loop ---

2. 0번째 배열의 시간 * 배열 크기 를 k에서 빼기

3. 모든 배열에서 0번째 배열의 시간만큼 빼주고

   시간이 0이 되는 index는 vector의 erase함수를 활용해서 없애기

--- loop end ---

4. 남은 배열의 크기 > k 라면 %를 활용해서 index 구하기.

   아니라면 -1 !!

 

이렇게하니 정확성은 다 맞았지만 효율성에서는 한개 빼고 다 시간초과가 뜨더군요..ㅠㅠ

 

후에 정답 코드를 확인하고 보니 3번 과정은 전혀 쓸모가 없는 과정이었습니다.. 

배열의 시간들을 일일이 빼줄 필요도 없었고 erase할 필요도 없었습니다.. 

그저 이전 index의 시간과의 차이를 이용하면 끝이었습니다!

코드를 보고나면 엄청 쉬운 문제지만 이렇게 바로 생각해내기가 너무 어려운 것 같습니다..

 

아래는 풀이한 코드입니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
 
bool sort_by_idx(pair<ll,int> a, pair<ll,int> b) {
    return a.second < b.second;
}
int solution(vector<int> food_times, ll k) {
    vector<pair<ll, int>> times;
    for (int i = 0; i < food_times.size(); i++) {
        times.push_back({ food_times[i], i + 1 });
    }
    sort(times.begin(), times.end());
    int n = times.size();
    int i = 0;
    for (; i < n; i++) {
        ll diff = (i == 0 ? times[0].first : times[i].first - times[i - 1].first);
        ll total = diff * (n - i);
        if (k - total < 0) break;
        else k -= total;
    }
    if (i == n) return -1;
    k %= (n - i);
    sort(times.begin() + i, times.end(), sort_by_idx);
    return times[i + k].second;
}
int main(void) {
    //vector<int> food_times = { 6,6,6,6,6,6,6 };
    //long long k = 40;
    vector<int> food_times = { 3, 1, 2 };
    long long k = 6;
    cout << solution(food_times, k);
    return 0;
}

 

질문이나 지적사항은 댓글 부탁드립니다:)