구현

프로그래머스 2019 KAKAO BLIND RECRUITMENT Level 4 문제 무지의 먹방 라이브를 Java를 이용해 풀어보았다. Level 4 문제를 도움 없이 온전히 혼자의 힘으로 푼 건 처음이다. 기분이 째진다. 하지만 2시간이 걸렸다. 그래도 포기 안하고 끝까지 어떻게든 풀어보려고 발버둥친 건 칭찬해...

문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/42891

DFS 사용

처음에 생각했던 방법은 문제에서 주어진 k번을 다 탐색하며 0인 놈은 건너 뛰어주며 마지막에 만나게 된 0이 아닌 값의 index+1 을 답으로 구하려 했는데 그럼 당연히 효율성 테스트 통과를 못 할 것이 뻔해서 완전 탐색이 아닌 로직을 짜려고 고민했다.

내가 짠 로직의 구조는 다음과 같다.

말로 표현하려고 하니까 진짜 어려운데 그 말인즉슨, 사실 나도 내 로직을 완벽하게 이해하지 못했다는 뜻...
무언가를 이해했다는 것은 가장 간단하게 설명할 수 있다는 것이란 파인만 형님의 말씀에 따라... 나는 사실 내 풀이조차 이해를 하지 못한 것...ㅠ

모든 음식에 대해서 다 먹어서 더이상 먹을 것이 없을 때는 -1을 반환해야 하는 예외 경우는 6번 작업에서 모든 음식들에 대해 탐색할 때 0인 녀석들을 만날 때마다 flag값을 0부터 시작해 계속 1씩 추가해주며 모든 음식에 대해 탐색이 끝났을 때 flag값이 음식의 개수와 같으면 그냥 -1을 반환하도록 했다.

말이 존나게 어려운데 이를 코드로 옮기면 다음과 같다.

public class MukBang {
    static int answer;

    static int solution(int[] food_times, long k) {
        int foodNum = food_times.length; 
        long round = k / foodNum; // 온전한 바퀴수

        dfs(food_times, foodNum, round, k);
        return answer;
    }

    static void dfs(int[] food_times, int foodNum, long round, long idx){
        if(idx<=foodNum){ // 인덱스가 음식의 개수 이하일 때 재귀를 종료해주자. 
            while(idx>=0){
                int flag = 0;
                for (int i = 0; i < foodNum; i++) {
                    if (food_times[i] == 0) { // 다 먹은 음식 개수 세고 바로 넘기자
                        flag++;
                        continue;
                    }
                    if (idx == 0) {
                        answer = i+1;
                        return;
                    }

                    food_times[i] -= 1;
                    idx--;
                }
                if(flag==foodNum)   break; // 싹 다 먹어서 남은 거 없으면 while문 종료
            }
            answer = -1; // while문 종료돼서 여기로 왔다는 건 결국 더이상 먹을 게 없다는 뜻
            return;
        }

        idx %= foodNum; // 온전한 바퀴수를 돌고나서 몇 번째 음식에 도달했는지
        for(int i=0; i<food_times.length; i++) {
            if (food_times[i] < round) // 뛰어 넘어야 할 녀석들이 있었다면
                idx += (round - food_times[i]); // 몇 번이나 뛰어넘었는지 idx에 추가해주자
            food_times[i] = (food_times[i]-round<0 ? 0 : food_times[i]-(int)round); // 다 먹었으면 0, 아직 남아있으면 남은 양으로 갱신
        }
        dfs(food_times, foodNum, idx/foodNum, idx);
    }

    public static void main(String[] args) {
        int[] food_times = {3,1,1,3};
        int k = 7;
        int answer = solution(food_times, k);
        System.out.println(answer);
    }
}

가끔 다른 사람들의 풀이를 보며 이해하려고 영혼을 다 해 코드를 살펴보지만 도저히 이해가 안 될 때가 있다. 나의 위 코드가 다른 사람 입장에서 그렇지 않을까 싶다.... 죄송합니다.

오늘 배운 것

1. 끝까지 포기하지 말자!
2. 나도 내 풀이를 이해하지 못하더라도.. 맞히면 그만 ㅎ