프로그래머스 알고리즘 : 도둑질 (java)

프로그래머스 알고리즘 (java)

도둑질

프로그래머스 (도둑질)

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

코드리뷰

조건

• 1번째 집을 털면 마지막 집은 털지 못한다.
• 인접한 집은 털지 못한다.

풀이방향

인접한 집을 털지 못하니 1번집을 털 경우와 2번집을 털 경우 그리고 한 칸씩 띄워서 두개의 최대 값을 비교하면 된다 생각하고 문제를 풀었습니다. 하지만 두칸 건널 수도 있다는 경우를 생각 못해 문제 풀기에 실패 했습니다.

money[i] 의 값이 주어 졌을 때 이 값을 포함한 최대 값을 구하여 전체를 다 탐색하는 방법으로 풀었습니다.

money[i] 를 포함한 최대 값 result[i + 2] 는 두 칸 뒤에 있는 result[i] 와 3칸 뒤에 있는 result[i - 1] 값 중 큰 값을 선택 하면 됩니다.

코드

public class Thievery {
    public int solution(int[] money) {
        int answer = 0;
        //첫번째 집부터 구하기
        int[] result = new int[money.length + 2];
        //두번째 집부터 구하기
        int[] result2 = new int[money.length + 2];

        //초기값 입력
        result[2] = money[0];
        result2[3] = money[1];

        //i를 증가 시키면서 money[i] 를 사용할 때 최고 값을 구한다.
        for (int i = 1; i < money.length; i++) {
            // dp
            //첫번째 집을 구할땐 마지막 집을 못 더한다.
            if (i < money.length - 1) {
                dp(money, result, i);
            }
            //두번째 집부터 구하려면 첫번째 집은 못 더한다.
            if (i > 1) {
                dp(money, result2, i);
            }
            //나온 결과 값들중 가장 큰값을 뽑는다.

            answer = findMax(answer, result[i + 2], result2[i + 2]);
        }

        return answer;
    }

    private int findMax(int answer, int result1, int result2) {
        int newResult = result1 > result2 ? result1 : result2;
        if (answer > newResult) {
            return answer;
        }
        return newResult;
    }

    private void dp(int[] money, int[] result, int i) {
        if (result[i] > result[i - 1]) {
            result[i + 2] = money[i] + result[i];
        } else {
            result[i + 2] = money[i] + result[i - 1];
        }
    }
}

느낀점

문제가 정말 어렵다고 느껴 졌습니다. 저는 집을 기준으로 하나씩 띄워 계산을 하는 방법을 생각 했는데 너무 로직이 복잡해지고 답도 계속 다르게 나와 맨탈이 터져 검색을 해보니 다른사람들이 푼 코드를 봤는데 정말 천재들은 많구나 다시 한번 느꼈습니다.

그분들의 풀이를 참고해 money[i] 를 기준으로 다 확인 해 주니 문제가 풀렸습니다. 정말 어렵지만 재밌는 문제였고 한번 더 발전하는 계기가 된거 같습니다.

참조

https://chaibin0.tistory.com/entry/도둑질