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

문제 상황

인접한 숫자를 제외하고 선택한 숫자들의 최대 합을 구하는 문제. 배열이 원형으로 연결되어 있어 마지막과 첫 번째가 인접.

첫 번째 시도: 선형 배열로 접근

function maxSumNoAdjacent(nums) {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];
    if (nums.length === 2) return Math.max(nums[0], nums[1]);

    const dp = new Array(nums.length);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);

    for (let i = 2; i < nums.length; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }

    return dp[nums.length - 1];
}

문제점:

• 원형 연결을 고려하지 않음
• 마지막과 첫 번째가 인접한 제약을 무시

두 번째 시도: 원형 배열 고려

function maxSumNoAdjacentCircular(nums) {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];
    if (nums.length === 2) return Math.max(nums[0], nums[1]);

    // 경우 1: 첫 번째 포함, 마지막 제외
    const case1 = maxSumLinear(nums.slice(0, nums.length - 1));

    // 경우 2: 첫 번째 제외, 마지막 포함
    const case2 = maxSumLinear(nums.slice(1));

    return Math.max(case1, case2);
}

핵심 아이디어:

• 원형을 두 가지 선형 케이스로 분해
• 첫 번째 포함/제외로 나눠 각각 계산 후 최댓값 선택

왜 실수했나

• 문제 조건을 충분히 분석하지 않음
• 선형 배열 패턴에만 의존
• 원형 연결이라는 핵심 제약을 놓침

회고

• 문제 조건을 정확히 파악
• 선형/원형 등 구조적 차이를 명확히 구분
• 단순한 패턴 적용보다 문제 특성에 맞는 접근 필요

올바른 접근법

1. 문제 분석: 원형 연결 여부 확인
2. 케이스 분리: 원형을 선형으로 분해
3. 각 케이스 해결: 기존 알고리즘 적용
4. 결과 비교: 최댓값 선택

결론

원형 배열 문제는 선형 배열과 다른 접근이 필요하다. 조건을 정확히 읽고, 원형을 선형 케이스로 분해해 해결하는 것이 핵심이다.