2019 카카오 신입 공채 1차 코딩 테스트 풀이 - 4번문제

2018-10-08 01:24:36 | 조회수 2103



4번 문제는 효율성 테스트와 정확성 테스트의 2가지 영역으로 나눈 테스트입니다.


따라서 2가지로 나누어 풀어보도록 하겠습니다.


1) 정확성


정확성의 경우 k의 범위가 200만이므로 정말로 하나씩 다 먹어보면서, 음식의 개수가 0이 되면 사라지는 방식으로 다음에 먹어야 할 음식이 무엇인지 알 수 있습니다.


2) 효율성


효율성 테스트는 k의 범위가 $10^{13}$ 을 넘어가므로 모두 해볼 수 없습니다. 따라서, 이번에는 다른 방법으로 생각을 해봐야 합니다. 모든 경우를 다 해보는 것이 아니라, 어떤 특정 음식을 다 먹었을 때, 그 음식을 다 먹기까지 걸리는 개수를 구해보는 것입니다.


예를 들어



5

4

7

2

4


로 음식이 배치 되어있다고 하면, 가장 먼저 다 먹게 되는 음식은 바로 4번이며, 다 먹는 시점은 9초입니다. 이걸 조금 다르게 표현을 하면, "적어도 음식의 개수(5) * 음식의 양(2) 인 10초 이내에는 4번 음식을 다 먹을 수 있다" 라고 표현할 수 있습니다. 이렇게 표현하게 되면, 이제 k가 10보다 같거나 작다면 이 범위 내에서 나머지 연산을 통해 어떤 음식을 먹는지 $O(1)$에 알 수 있습니다.


이제 4번 음식을 다 먹으면 남은 음식은 4개이고, 2번 음식과 5번 음식이 그 다음으로 다 먹게 될 음식이 됩니다. 이 때, 위에서 표현했던 원리로 "2번 음식은 적어도 8초 이내에는 다 먹을 수 있다" + 10 = "2번 음식은 적어도 18초 이내에는 다 먹을 수 있다" 가 됩니다. 이런 식으로 모든 경우를 다 해 볼 필요 없이, 음식의 개수가 0이 되어 사라지는 경우를 분기로 하여, 그 범위 내에 k가 포함이 될 경우를 찾은 다음 나머지 연산을 통해 해결할 수 있습니다.


음식의 개수가 적은 것부터 확인을 해야 하므로, 정렬이 필요합니다. 그 다음 음식의 개수만큼 돌며 확인합니다. 따라서 음식의 개수 $N$에 대해 $O(NlogN)$ 으로 풀 수 있습니다.


소스코드는 효율성 테스트 코드만 올립니다.


※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.

#include <algorithm>
#include <vector>
typedef long long ll;
using namespace std;

class Node {
public:
    ll no, amount;
    Node() {}
    Node(ll n, ll a) {
        no = n, amount = a;
    }
    bool operator <(const Node &n) const {
        return amount == n.amount ? no < n.no : amount < n.amount;
    }
} v[200011];

bool cmp(Node &a, Node &b) {
    return a.no < b.no;
}

int solution(vector<int> t, long long k) {
    ll sum = 0;
    v[0] = { 0,0 };
    for (int i = 1; i <= t.size(); i++) {
        v[i] = { i, t[i - 1] };
        sum += t[i - 1];
    }
    if (sum <= k) return -1;
    sort(v + 1, v + t.size() + 1);

    for (int i = 1; i <= t.size(); i++) {
        ll time = (v[i].amount - v[i - 1].amount) * (t.size() - i + 1);
        if (k <= time) {
            sort(v + i, v + t.size() + 1, cmp);
            k %= (t.size() - i + 1);
            k += i;
            return v[k].no;
        }
        k -= time;
    }
    return -1;
}


2019 카카오 신입 공채 1차 코딩 테스트 풀이 - 4번문제 - 알고리즘닷컴
32 개의 글