[프로그래머스] 스티커 모으기(2) / Java

문제주소 :programmers.co.kr/learn/courses/30/lessons/12971

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

---

<문제 설명>

문제 설명

N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다.

원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다.

예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다. 스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 하는 solution 함수를 완성해 주세요. 원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다.

제한 사항

• sticker는 원형으로 연결된 스티커의 각 칸에 적힌 숫자가 순서대로 들어있는 배열로, 길이(N)는 1 이상 100,000 이하입니다.
• sticker의 각 원소는 스티커의 각 칸에 적힌 숫자이며, 각 칸에 적힌 숫자는 1 이상 100 이하의 자연수입니다.
• 원형의 스티커 모양을 위해 sticker 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어있다고 간주합니다.

---

입출력 예

sticker                                                                 answer

[14, 6, 5, 11, 3, 9, 2, 10]	36
[1, 3, 2, 5, 4]	8

입출력 예 설명

입출력 예 #1
6, 11, 9, 10이 적힌 스티커를 떼어 냈을 때 36으로 최대가 됩니다.

입출력 예 #2
3, 5가 적힌 스티커를 떼어 냈을 때 8로 최대가 됩니다.

 

<풀이법>

▒ 한줄 개념: 동적 프로그래밍 ▒ 

가장 많이 등장하는 동적 프로그래밍 문제 유형 중 하나이다. 조건이 까다롭게 느껴질 수 있는데, 생각보다 그렇게 까다롭지는 않다. 두 가지의 핵심만 생각하면 된다.

 

1. dp[i] = sticker[i] + max(dp[i-2], dp[i-3])

2. 첫 번째, 마지막 스티커는 공존할 수 없다.

 

 

---

1. dp[i] = sticker[i] + max(dp[i-2], dp[i-3])

 

a. dp[i-2]: 최댓값을 가져야 하므로, 더 많은 스티커를 뗄 수 있는 방법이 최선일 수 있다. 하지만 양쪽이 안되므로, dp[i-1]은 당연히 선택할 수 없다. 그럼 바로 dp[i-2]를 선택하는 것이 가장 많은 스티커를 뗄 수 있는 방법이 될 것이다. 따라서 dp[i-2]는 첫 번째 옵션이다.

첫 번째 옵션!

 

b. dp[i-3]: dp[i-2]를 가져올 경우, dp[i-2]의 바로 양 옆인 dp[i-1], dp[1-3]은 선택할 수 없다. dp[i-1]은 어차피 dp[i] 입장에서도 가질 수 없는 값이니, 포기한다. 다만 dp[i-3]의 경우는? 혹시 dp[i-3]의 위치에 dp[i-2]의 값보다 큰 값이 있다면, 가져가야만 한다. 따라서 dp[i-3]이 두 번째 옵션이 된다.

 

두 번째 옵션!

 

2. 첫 번째, 마지막 스티커는 공존할 수 없다.

첫 번째, 마지막 스티커는 배열 상 멀리 있지만 실제로는 양 옆에 있다. 따라서 절대 둘은 동시에 떼어질 수 없다. 동적 계획법을 더 잘하시는 분들은 이를 해결하기 위해 dp를 2차원 배열로 선언하기도 하시던데, 조금 더 간단한 방법을 사용하였다. 어차피 둘다 사용할 수 없으니, 애초에 스티커를 두 개로 나누는 것이다.

이렇게 구현할 경우 공간적 효율성은 좀 떨어질 수 있더라도, 훨씬 구현의 개념이 단순해진다.

 

<코드(Java)>

class Solution {
    int[] dp1, dp2;
    int[] sticker2;
    public int solution(int sticker[]) {
        dp1 = new int[sticker.length];
        dp2 = new int[sticker.length];
        this.sticker2 = sticker.clone();
        
        if(sticker.length == 1)
            return sticker[0];
        
        dp1[0] = sticker[0];
        
        sticker[sticker.length-1] = 0;
        
        for(int i = 1; i < sticker.length; i++){
            if(i == 1){
                dp1[i] = sticker[i];
                dp2[i] = sticker2[i];
            }else if(i == 2){
                dp1[i] = sticker[i] + dp1[0];
                dp2[i] = sticker2[i] + dp2[0];
            }else{
                dp1[i] = sticker[i] + max(dp1[i-2], dp1[i-3]);
                dp2[i] = sticker2[i] + max(dp2[i-2], dp2[i-3]);
            }
        }
        
        int max1 = max(dp1[sticker.length-1], dp1[sticker.length-2]);
        max1 = max(max1, dp2[sticker.length-1]);
        return max(max1, dp2[sticker.length-2]);
    }
    
    int max(int a, int b){
        return a > b ? a : b;
    }
}

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest