프로그래머스: 스티커 모으기 2 [JAVA]

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/12971

코딩테스트 연습 - 스티커 모으기(2)

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 쉽게 풀을 수 있는 sticker 배열 길이가 4 이하인 경우 단순히 뽑아 비교
2. 그보다 긴 sticker 배열에 대해선 2개의 dp 배열(마지막 값 포함되는 경우, 마지막 값 포함안하는 경우)을 통해 누적 값 (현 위치 기준 2번째, 3번째 인덱스 뒤 dp 배열 중 최대값 + 해당 위치 스티커 값)
   1. 마지막 값이 포함되는 경우 인덱스 1까지 누적 값 계산(마지막 스티커를 뽑으면 첫 번째 스티커를 뽑을 수 없기 때문)
   2. 마지막 값이 포함되지 않는 경우 인덱스 0까지 누적 값 계산
3. 마지막 값이 포함된 dp 배열의 경우 1, 2 인덱스 위치의 누적 값, 마지막 값이 포함되지 않은 dp 배열의 경우 0, 1 인덱스 위치의 누적 값을 비교해 최대값 반환

 이 문제는 원이라는 특수성 때문에 고려해야할 상황이 늘어나는 문제이다. 만약 주어진 sticker 배열이 일직선 상이고, 여기서 스티커들을 골라야 한다면 하나의 dp 배열을 통해 dp[n] = max(dp[n+2], dp[n+3]) + sticker[n]의 점화식을 처음과 끝에서 진행하면 되지만, 원의 경우 0번째 스티커를 뽑는 순간 마지막 스티커 또한 사용하지 못한다.

 이렇게 첫 번째를 뽑느냐 마느냐에 따라 경우가 나뉘어지기 때문에 dp 배열도 2개를 준비해야 한다. 우선 마지막 스티커가 누적값 계산에 포함되는 경우에는 dp[n] = max(dp[n+2], dp[n+3]) + sticker[n] 점화식을 진행하며 인덱스 0이 아닌 1까지 계산을 진행하고, 마지막 스티커가 누적값 계산에 포함되지 않는 경우엔 해당 점화식을 인덱스 0까지 진행하면 된다.

 이후 계산이 완료되면 마지막 값이 포함된 dp 배열의 경우 1, 2 인덱스 위치의 누적 값, 마지막 값이 포함되지 않은 dp 배열의 경우 0, 1 인덱스 위치의 누적 값을 비교해 최대값 반환하면 된다.

 

class Solution {
    public int solution(int sticker[]) {
        int answer = 0, length = sticker.length;

        if (length <= 3) {//길이가 3이하
            for (int i = 0; i < length; i++) {
                answer = Math.max(answer, sticker[i]);
            }

            return answer;
        } else if (length == 4) {//길이가 4인 경우
            return Math.max(sticker[0] + sticker[2], sticker[1] + sticker[3]);
        }

        int[] dp1 = new int[length], dp2 = new int[length - 1];

        //각각 dp 배열의 뒤에 숫자 3개를 채워놓음
        dp1[length - 1] = sticker[length - 1];
        dp1[length - 2] = sticker[length - 2];
        dp1[length - 3] = sticker[length - 3] + dp1[length - 1];
        dp2[length - 2] = sticker[length - 2];
        dp2[length - 3] = sticker[length - 3];
        dp2[length - 4] = sticker[length - 4] + dp2[length - 2];

        for (int i = length - 4; i > 0; i--) {//탐색 반복
            dp1[i] = sticker[i] + Math.max(dp1[i + 2], dp1[i + 3]);
            dp2[i - 1] = sticker[i - 1] + Math.max(dp2[i + 1], dp2[i + 2]);
        }

        return Math.max(Math.max(dp1[1], dp1[2]), Math.max(dp2[1], dp2[0]));
    }
}

결과