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

문제

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

프로그래머스

 

---

 

문제 개요

주어진 스티커 배열에서 서로 인접한 스티커를 선택하지 않으면서 스티커에 적힌 숫자의 합을 최대화하는 문제입니다. 스티커가 원형으로 연결되어 있다는 점에서 첫 번째 스티커를 선택하면 마지막 스티커는 사용할 수 없다는 제약이 있습니다.

접근 방법

1. 원형 배열 처리: 스티커가 원형으로 연결되어 있기 때문에 첫 번째 스티커와 마지막 스티커를 동시에 선택할 수 없습니다. 이를 해결하기 위해 두 가지 경우로 나눠서 생각합니다.
   • 첫 번째 스티커를 선택하는 경우
   • 첫 번째 스티커를 선택하지 않는 경우
2. 동적 계획법(DP) 활용: 인접한 스티커를 선택할 수 없다는 제약 때문에 동적 계획법을 사용하여 최댓값을 구합니다. 각 스티커 위치에서 그 스티커를 선택했을 때의 최댓값을 계산하며 배열을 업데이트합니다.
3. 케이스 분리:
   • 첫 번째 스티커를 선택하는 경우, 마지막 스티커는 선택할 수 없으므로 마지막 스티커를 제외하고 최대 합을 구합니다.
   • 첫 번째 스티커를 선택하지 않는 경우, 첫 번째 스티커를 제외하고 최대 합을 구합니다.
4. 최종 결과: 두 경우에서 구한 최대값을 비교하여 최종 결과를 도출합니다.

해결 과정

1. 배열 초기화:
   • a: 첫 번째 스티커를 선택하는 경우의 최댓값을 저장하는 배열.
   • b: 첫 번째 스티커를 선택하지 않는 경우의 최댓값을 저장하는 배열.
2. 동적 계획법 적용:
   • a[i]: i번째 스티커를 선택하는 경우, 두 칸 전의 값에 현재 스티커 값을 더한 것과 바로 이전 값 중 최댓값을 저장.
   • b[i]: 첫 번째 스티커를 선택하지 않는 경우에도 동일한 방식으로 값을 계산.
3. 최댓값 계산:
   • a[a.length - 2]: 첫 번째 스티커를 선택한 경우 마지막 스티커를 제외하고 최댓값.
   • b[b.length - 1]: 첫 번째 스티커를 선택하지 않은 경우 마지막 스티커까지 포함한 최댓값.
   • 두 값 중 더 큰 값을 반환.

주요 포인트

• 원형 구조 처리: 첫 번째 스티커를 선택하면 마지막 스티커는 사용할 수 없다는 제약을 적절히 처리하기 위해 두 가지 경우로 나누어 문제를 해결합니다.

import java.util.*;
class Solution {
    public int solution(int sticker[]) {
        int answer = 0;
        if(sticker.length == 1) return sticker[0];
        int[] a = new int[sticker.length];
        int[] b = new int[sticker.length];
        
        a[0] = a[1] = sticker[0];
        b[1] = sticker[1];
        
        for(int i=2; i<sticker.length; i++) {
            if(i != sticker.length-1)a[i] = Math.max(a[i-2]+sticker[i], a[i-1]);            
            b[i] = Math.max(b[i-2]+sticker[i], b[i-1]);
        }

        return Math.max(a[a.length-2], b[b.length-1]);
    }
}