[프로그래머스 Level.3] 스티커 모으기(2) (Summer/Winter Coding(~2018)) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > Summer/Winter Coding(~2018) > 스티커 모으기(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로 최대가 됩니다.

 

 

 

 

 

나의 코드

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

        int[] dp1 = new int[sticker.length]; // 0 인덱스 시작
        int[] dp2 = new int[sticker.length]; // 1 인덱스 시작
        
        // dp1 : 첫 번째 스티커를 떼는 방법 -> 마지막 원소 사용 X
        dp1[0] = sticker[0];
        dp1[1] = sticker[0];
        for(int i=2; i<sticker.length-1; i++) {
            dp1[i] = Math.max(dp1[i-1], dp1[i-2] + sticker[i]); // 해당 인덱스까지 최댓값 계속 갱신
        }
        
        // dp2 : 첫 번째 스티커를 떼지 않는 방법 -> 마지막 원소 사용 O
        dp2[0] = 0;
        dp2[1] = sticker[1];
        for(int i=2; i<sticker.length; i++) {
            dp2[i] = Math.max(dp2[i-1], dp2[i-2] + sticker[i]); // 해당 인덱스까지 최댓값 계속 갱신
        }

        answer = Math.max(dp1[sticker.length-2], dp2[sticker.length-1]);
        
        return answer;
    }
}

 

풀이

1. 이러한 원형 구조의 경우 첫 번째 스티커를 선택하면 마지막 스티커를 선택 할 수 없고 첫 번째 스티커를 선택하지 않으면 마지막 스티커를 선택 할 수 있다. 따라서 두 가지의 경우로 나누고 각각 dp를 이용해 각각 최댓값이 되는 경우를 구하고 두 dp의 최댓값을 비교해 최종적으로 최댓값을 구하면 된다.
2. 우선 sticker.length가 1이라면 스티커가 한 개 뿐이므로 해당 스티커의 값을 리턴한다.
3. 첫 번째 스티커를 떼는 경우에서 최댓값을 구하는 int형 배열 dp1과 첫 번째 스티커를 떼지 않는 경우에서 최댓값을 구하는 int형 배열 dp2를 생성한다.
4. dp1에서는 첫 번째 스티커를 떼므로 dp[0]에 첫 번째 스티커의 값인 sticker[0]이 들어가고 첫 번째 스티커를 뗐으므로 붙어 있는 sticker[1]을 뗄 수 없으므로 dp[1]에도 sticker[0]을 저장한다.
5. 그리고 index가 2부터 마지막 스티커 전인 sticker.length-2까지 for문을 돌리면서 해당 인덱스의 스티커와 전전 스티커를 뗐을 때의 경우(dp1[i-2] + sticker[i])와 바로 전 스티커를 뗐을 경우(dp1[i-1])를 비교하여 큰 값으로 dp1[i] 값을 업데이트 한다.
6. dp2에서는 첫 번째 스티커를 떼지 않는 방법이므로 dp2[0]는 0이고 첫 번째 스티커를 떼지 않았으므로 두 번째 스티커를 떼는 것이 dp2[1]의 최댓값이므로 dp2[1]에는 sticker[1]을 저장한다.
7. 그리고 index가 2부터 마지막 스티커인 sticker.length-1까지 for문을 돌면서 마찬가지로 해당 인덱스의 스티커와 전전 스티커를 뗐을 때의 경우(dp2[i-2] + sticker[i])와 바로 전 스티커를 뗐을 경우(dp2[i-1])를 비교하여 큰 값으로 dp2[i] 값을 업데이트 한다.
8. 마지막으로 dp1의 마지막 스티커 전까지의 최댓값인 dp1[sticker.length-2]와 dp2의 마지막 스티커까지의 최댓값인 dp2[sticker.length-1]를 비교하여 큰 값을 answer에 저장하고 반환한다.