[알고리즘 - 그리디] 무지의 먹방 라이브

문제

문제 링크 - 프로그래머스

그렇다고 합니다. 무지가 갑자기 얄미워보이는 마법의 코테

결국 정리하면 0, 1, …, n초 동안 주어진 음식을 먹는데 k초뒤에 어떤 음식을 먹고있을지 출력하는 문제이다. 단순하게 k번 루프를 돌리면 답이 나오긴 하곘지만 입력 범위가 엄청 크기 때문에 다른 방법을 써야 될 것 같았다.

풀이 방법

그래서 처음에 생각한 방법은 이렇다.

1. LinkedList에 주어진 음식(섭취에 걸리는 시간)들을 모두 넣어 오름차순으로 정렬
   1. 정렬되기 이전 순서대로 ArrayList로도 하나 만들어두고 두 list가 같은 객체들을 참조하도록 해준다
2. 루프안에서 현재 count를 기억해두고 현재와 동일한 시간을 갖는 음식을 removeFirst() - O(1) 으로 제거
   1. 이때 음식의 시간을 0으로 변경해주고 제거하기 (나중에 ArrayList에서 순회 시 사용)
   2. 모든 원소를 순회하는게 아니라 현재 count와 동일한 원소만 순회하므로 시간이 줄어든다
3. 네트워크가 중단될 시간 k에서 현재 LinkedList 크기를 뺴준다 (원소 개수만큼의 시간동안 음식을 먹은 셈이므로)
4. 만약, 매 순회 시 남은 k가 LinkedList의 크기보다 작다면, 남은 음식을 모두 먹기 전에 k초에 도달한다는 의미이므로 남은 음식 중 k번째 음식을 반환한다
   1. 이때, 정답을 반환할 때 이미 다 먹은 음식의 index도 고려해야 하므로 앞서 만들어둔 정렬되지 않은 ArrayList를 순회하며 음식시간이 0이 되지 않은 음식을 만날 때 마다 k-- 를 해주고 k == 0 이 되는 순간의 음식 index를 반환하면 답을 찾을 수 있다.
5. 만약, k == 0이 됨과 동시에 남은 음식이 없는 경우 혹은 k > 0 인데 음식이 남아있는 경우 더 이상 먹방을 진행할 수 없으므로 -1을 반환한다.

위 방법으로 작성한 코드는 아래와 같고, 정확성 / 효율성 테스트 모두 일단 통과했다.

import java.util.*;
import java.util.stream.*;

class Solution {

    static class Food implements Comparable<Food> {
        public int time = 0;

        public Food(int time) {
            this.time = time;
        }

        @Override
        public int compareTo(Food other) {
            return this.time - other.time; // 오름차순
        }
    }

    public int solution(int[] food_times, long k) {
        List<Food> foods = Arrays.stream(food_times)
            .mapToObj(Food::new)
            .collect(Collectors.toList());

        LinkedList<Food> sortedFoods = new LinkedList<>(foods);
        Collections.sort(sortedFoods);

        int iterCount = 0;
        while (k >= 0 && sortedFoods.size() > 0) {
            iterCount++;
            if (k >= sortedFoods.size()) {

                k -= sortedFoods.size();

                while (!sortedFoods.isEmpty()) {
                    Food current = sortedFoods.getFirst();
                    if (current.time <= iterCount) {
                        current.time = 0;
                        sortedFoods.removeFirst();
                    } else {
                        break;
                    }
                }   
            } else {
                int index = -1;
                while (k >= 0) {
                    index++;
                    if (foods.get(index).time == 0) {
                        continue;
                    }
                    k--;
                }
                return index + 1; // 문제의 index는 1부터 시작
            }
        }
        // 더 이상 섭취할 수 있는 음식이 없는 경우
        return -1;
    }
}

개선(?) 해보기

현재는 Food가 index를 포함하지 않아서 index를 별도로 계산해주어야 하고 리스트도 2개하다는 문제가 있다. 이를 개선해볼 수 있을 것 같았다.

먼저 Food를 이렇게 변경해줬다

static class Food {
    public int time;
    public int index;

    public Food(int time, int index) {
        this.time = time;
        this.index = index;
    }
}

그리고 LinkedList를 먼저 시간으로 정렬한 후 기존에 k와 리스트를 업데이트하는 작업을 수행하고 k가 남은 음식 수보다 작을 때 수행하는 연산은 다시 해당 List를 index로 정렬 후 수행해준다.

import java.util.*;
import java.util.stream.*;

class Solution {

    static class Food {
        public int time;
        public int index;

        public Food(int time, int index) {
            this.time = time;
            this.index = index;
        }
    }

    public int solution(int[] food_times, long k) {
        LinkedList<Food> foods = new LinkedList<>();
        for(int i = 0 ; i < food_times.length ; i++) {
            foods.add(new Food(food_times[i], i + 1));
        }

        // 먼저 시간으로 오름차순 정렬
        Collections.sort(foods, (f1, f2) -> f1.time - f2.time);

        int iterCount = 0;
        while (k >= 0 && foods.size() > 0) {
            iterCount++;
            if (k >= foods.size()) {

                k -= foods.size();

                while (!foods.isEmpty()) {
                    Food current = foods.getFirst();
                    if (current.time <= iterCount) {
                        current.time = 0;
                        foods.removeFirst();
                    } else {
                        break;
                    }
                }   
            } else {
                // index로 오름차순 정렬
                Collections.sort(foods, (f1, f2) -> f1.index - f2.index);
                return foods.get((int) k).index;
            }
        }
        // 더 이상 섭취할 수 있는 음식이 없는 경우
        return -1;
    }
}

코드는 간결해졌는데 sort를 두번 수행하게 되어 어째 시간복잡도는 늘어난거같다. 획기적으로 시간을 줄일 수 있는 코드도 있는 것 같은데 아직 그런 풀이를 스스로 떠올리지는 못하겠어서 그리디 문제를 좀 더 풀어보고 다시 고민해보면 좋을 것 같다.