프로그래머스 - 12971 : 스티커 모으기(2) - 문제 풀이 ( 자바 / java)

📌문제 설명

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로 최대가 됩니다.

---

🪄 풀이법

먼저 문제를 읽고 어떻게 풀어봐야할지 생각해 보았다.

문제는 선택하고 안하고의 경우를 따져서 푸는 재귀로 풀거나 DP 로 풀 수 있다고 생각했다.

그리고 N 을 보았을 때 100,000 이니 재귀로는 절대 못풀고 이중 for문을 쓰는 O(N^2) 도 불가하고 DP로 풀어야 겠다고 생각했다.

 

첨엔 막연하게 홀수 인덱스를 전부고르거나, 짝수 인덱스를 전부 골라 이 두가지 경우의 수중 합이 큰걸 골라도 되나? 생각하기 쉽지만

[ 1, 22, 1, 1, 33, 1, 1, 1] 같이 큰수가 홀수 인덱스에도 하나 짝수 인덱스에도 한개 씩 있는 경우가 있기에 저렇게 단순 하게 풀면 안된다.

 

인덱스를 고르고 안 골랐을 경우를 생각하면서 DP로 풀어야 하는데, 문제의 스티커가 원형이기 때문에 0번째 인덱스를 살필 땐 맨 마지막 인덱스 까지 살펴봐야한다는 생각이 들었고, 그럼 배열의 크기가 3 이상 필요하겠구나 생각했다.

하지만 N은 1이상 부터 시작이기 때문에 N이 1 일때와 2일때 처리를 해줘야한다. 안그러면 마지막 테케에서 런타임에러가 생길 것이다.

 

처음엔 접근을 0번째 인덱스와 맨 마지막 인덱스를 고르는 케이스 두가지로 시작하려고 했지만, 너무 복잡한 것 같아. 0번 째와 1번째로 경우의 수를 나누었다.

 

[1, 2, 3, 4, 5, 6, 7, 8] 라는 스티커가 있는경우라면

 

스티커 1을 떼면서 시작하는 경우 (0번 째 인덱스)
[1, 2, 3, 4, 5, 6, 7] 만 가지고 dp를 사용하면 된다. ( 0번째를 고름으로서 맨마지막 인덱스의 수를 못 고르기 때문)

 

스티커 2를 떼면서 시작하는 경우 (1번째 인덱스)
[2, 3, 4, 5, 6, 7, 8] 만 가지고 dp를 사용하면 된다.

 

두 가지 케이스로 DP 문제 풀이를 하고 두가지 DP의 맨 마지막 값중 더 큰 값이 정답이 되게 된다.

 

1 - DP 풀이로 문제 접근

2 - 주어진 스티커 배열의 크기가 1일때, 2일때 예외처리

3 - 0번째 인덱스를 고를 경우, 1번째 인덱스를 고를 경우 두가지로 DP 처리

위의 3가지 경우를 생각해 내면 풀 수 있는 문제다.

 

 

💯 정답 코드

 1) 현재 위치를 뽑는 경우, dp[i - 2] + sticker[i]

 2) 현재 위치를 뽑지 않는 경우, dp[i - 1]

class Solution {
    public int solution(int sticker[]) {
        int size = sticker.length;
        if (size == 1) return sticker[0];
        else if (size == 2) return Math.max(sticker[0], sticker[1]);
 
        //0번째 인덱스를 고르면서 시작한 경우
        int[] dp1 = new int[size - 1];
        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]);
        }
 
        //1번째 인덱스를 고르면서 시작한 
        int[] dp2 = new int[size];
        dp2[0] = 0;
        dp2[1] = sticker[1];
 
        for (int i = 2; i < size; i++) {
            dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + sticker[i]);
        }
 
        return Math.max(dp1[dp1.length - 1], dp2[dp2.length - 1]);
    }
}