Today's Algorithm(2018-12-08)

programmers. 라면공장

• 다음 공급날까진 충분히 양이 남았지만 그 다음 공급날, 그 다다음 공급날까지 버텨내지 못하는 경우는 어떻게 처리해야할까요?

  • 그래서 dfs로 현재 상황에서 공급량이 충분히 되더라도 공급을 받는 경우, 그리고 공급을 받지 못하는 경우를 모두 실행하도록 구성하였습니다.

class Solution {
    int answer;
    int k;

    public int solution(int stock, int[] dates, int[] supplies, int k) {
        this.k = k;
        this.answer = supplies.length;
        dfs(stock, dates, supplies, 0, 0, 0);
        return answer;
    }

    public void dfs(int stock, int[] dates, int[] supplies, int today, int index, int num) {
        int nextSupplyDay = index + 1;
        if(nextSupplyDay < supplies.length) {
            if(dates[index] - today > stock) {  // 안되는 경우
                return;
            } else {  // 공급이 필요없는 경우
                stock = stock - today;
                boolean flag = false;
                if(!flag) {
                    dfs(stock + supplies[index], dates, supplies, dates[index], index + 1, num + 1);
                    flag = true;
                }
                if(!flag) {
                    dfs(stock, dates, supplies, dates[index], index + 1, num);
                }
            }
        } else {  // 마지막인 경우
            if(k - dates[index] > stock) {
                answer = Math.min(answer, num + 1);
            } else {
                answer = Math.min(answer, num);
            }
        }
    }
}

하지만 깔끔하게 모두 실패했습니다. 어디서 문제가 발생하였을까요..? 제가 짠 코드를 이해하지도 못할거면서 이렇게 짠건 참 책임감 없었던 것 같아요. 그래서 다른 사람의 코드를 참고하면서 PriorityQueue 로 풀기로 방향을 바꾸었습니다.

 

이 문제의 가장 고민되는 부분은 '해당 날짜에는 공급이 필요하지 않았지만 나중에 알고보니 그때 받았어야 했을 때'입니다. 이 부분에 대한 구현을 고민하다보니 위 코드에서 dfs라는 스스로 고난의 길을 빠뜨리기도 했었구요. 하지만 PriorityQueue를 사용하면 이 문제를 보다 쉽게 해결할 수 있습니다! 공급시점에서 당장 필요하지 않을 때는 PriorityQueue 에 넣어두고 꺼내지 않습니다. 그리고 나중에 필요한 시점이 되면 그때 큐에서 가장 큰 값을 꺼내는 것이죠. 여기서 가장 큰 값을 꺼내는 이유는 최대한 큰 양을 공급 받아둠으로써 공급 횟수를 줄이는 것이 문제의 요구사항이기 때문입니다. 코드로 나타내면 다음과 같습니다.

class Solution2 {
    public int solution(int stock, int[] dates, int[] supplies, int k) {
        int answer = 0;
        Queue<Integer> queue = new PriorityQueue(Collections.reverseOrder());

        int index = 0;
        for (int day = 0; day < k; day++) {
            if(index < dates.length && day == dates[index]) {  // index < dates.length는  index가 ++때문에 마지막에 초과index 되기때문
                queue.offer(supplies[index]);
                index++;
            }
            if(stock <= 0) {
                answer++;
                stock += queue.poll();
            }
            stock--;
        }
        return answer;
    }
}

위 코드에서 for문 안 두 개의 if문의 실행 순서가 중요합니다. 왜냐하면 다음 문제의 요구조건 때문입니다.

dates에 들어있는 날짜에 공급되는 밀가루는 작업 시작 전 새벽에 공급되는 것을 기준으로 합니다. 예를 들어 9일째에 밀가루가 바닥나더라도, 10일째에 공급받으면 10일째에는 공장을 운영할 수 있습니다.

공급은 새벽에 받기 때문에 queue.offer()이 먼저 선행되어야 queue안의 값을 poll() 할 수 있기 때문입니다. 만약 순서가 뒤바뀐다면 queue에 값이 안들어가 있어 NullPointException이 발생할 것입니다.

 

이 문제는 사고의 전환을 통해 정말 쉽게 풀 수 있었는데도 불구하고 전 그 방법을 생각하지 못하였습니다. 뭐.. 생각이 안나면 연습을 통해 이후에 생각나게 할 수 밖에 없죠. 생각이 나면 좋겠지만... 다음에 또 풀어봐야겠네요.