[programmers / kakao] 무지의 먹방 라이브 (Java)

문제

출처 : https://programmers.co.kr/learn/courses/30/lessons/42891?language=java# 

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

각 음식을 먹는데 필요한 시간이 있는 foodTimes[] 배열이 주어진다. 

항상 하나의 음식을 1초 먹은후, 다음 음식을 먹어야 하며, 음식은 1초동안 1만큼 먹을 수 있다.

(단, 음식의 양foodTimes[] 배열의 원소가 0일 경우에는 음식을 다 먹은것 이라고 판단하고 다음 음식을 먹는다.)

이때, K번째 먹을 음식을 찾는 문제다.

(정확히는 K초 후 네트워크 장애가 일어나고, 네트워크 장애가 해결된 후, 먹을 음식의 idx를 출력하는것 인데, 결국 K번째 먹을 음식을 물어보는거랑 똑같다)

---

풀이

약간의 아이디어가 필요한 구현문제였다.

(체감상 solved레벨 골드 4, 골드 5?? 정도 되는듯) 

위 사진보다 더 최적화 할수있는데, 방법은 글에 적어놨다.

아이디어)

효율성 테스트에서 K는 최대 2*10^13 까지 주어진다. 따라서, foodTimes를 하나씩 줄여가며 시뮬레이션을 돌리면 시간초과가 난다. 반면, foodTimes[] 배열의 최대 길이는 200,000이다. 즉, foodTimes배열은 200,000정도의 반복으로 처음부터 끝까지 확인할 수 있다. 

따라서, 이 문제의 관건은 "K를 foodTimes[] 배열의 사이즈 보다 빠르게 작게 만드는 방법이다." 이다.

 

시나리오)

1) K를 foodTimes[] 배열의 사이즈만큼 줄여준다. (단, foodTimes[] 배열의 원소가 0보다 작거나 같은경우 사이즈에 포함시키지 않는다.)

2) K의 크기가 foodTimes[] 배열의 사이즈보다 줄어들었다면, foodTimes를 실제로 하나씩 줄여가며 K번째 음식을 구한다. (마찬가지로 foodTimes[] 배열의 원소가 0보다 작거나 같은경우 사이즈에 포함시키지 않는다.)

 

아이디어 2)

위 시나리오을 읽어보면 foodTimes[] 배열의 사이즈를 구하는게 문제임을 알수있다.

foodTimes[]배열을 처음부터 끝까지 반복하며 원소가 0인 부분을 제외하는 방법으로 반복한다면, K를 줄여나갈때 마다 foodTimes.size()만큼 반복하므로 O(K*foodTimes.size())가 되어 시간초과를 피할 수 없다.

 

이 과정을 O(min(K, foodTimes.size()))만큼 줄일 수 있는데, 최소힙 (혹은) 오름차순으로 정렬된 Queue를 사용하는 방법이다.

K에서는 Queue.size()만큼 제외해주고, Queue에서는 "현재 반복 횟수"보다 작은 원소를 모두 제거해준다. 이때, Queue는 오름차순 정렬되어 있으므로, 반복회수는 O(min(K, foodTimes.size()))가 된다.

(최악의 경우 1억번 반복)

 

주요 소스코드

    private long optimizeK(int[] foodTimes, Queue<Integer> foodCycle, long k){
        int cycleCnt = 0;
        while(k >= foodCycle.size()){
            k -= foodCycle.size();
            cycleCnt++;
            this.deleteFoodCycle(foodCycle, cycleCnt);
        }
        this.deleteFoodTimes(foodTimes, cycleCnt);
        return k;
    }

 

+ 여기서 부터는 선택사항이며, 그냥 문제를 풀면서 생각한 최적화 방법인데, 내가 코드로 짜본게 아니라 실제로 풀릴지 모른다.

아이디어 2를 보면 알겠지만, 더 최적화 할 수 있는 방법이 존재한다.

K를 foodTimes의 사이즈만큼 제거해주는것이 아닌,

k = k - foodTimes의 가장 작은 값 * foodTimes의 사이즈 만큼 제거해주는것 이다.

이 과정에서 k가 음수가 될 수 있으므로, 적절히 처리해 줘야한다.

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/%5Bprogrammers%20kakao%5D%20%EB%AC%B4%EC%A7%80%EC%9D%98%20%EB%A8%B9%EB%B0%A9%20%EB%9D%BC%EC%9D%B4%EB%B8%8C/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃