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

문제 요약

숫자가 적힌 N개의 스티커가 원형으로 연결되어 있다.

하나의 스티커를 뜯으면 양옆에 인접한 스티커는 사용할 수 없다.

서로 인접하지 않은 스티커들을 선택해 얻을 수 있는 숫자 합의 최댓값을 구해야 한다.

원형 구조이므로 배열의 첫 번째 스티커와 마지막 스티커도 서로 인접해 있다.

핵심 아이디어

스티커가 일렬로 놓여 있다면 각 위치에서 다음 두 선택을 비교하는 동적 계획법으로 해결할 수 있다.

현재 스티커를 뜯지 않는 경우
현재 스티커를 뜯고 두 칸 전까지의 최댓값을 더하는 경우

하지만 이 문제의 스티커는 원형으로 연결되어 있다.

따라서 첫 번째 스티커와 마지막 스티커를 동시에 선택할 수 없다.

이 조건을 처리하기 위해 문제를 다음 두 경우로 나눈다.

첫 번째 스티커를 선택할 수 있는 경우
-> 마지막 스티커를 제외하고 계산

첫 번째 스티커를 선택하지 않는 경우
-> 첫 번째 스티커를 제외하고 계산

즉, 다음 두 선형 구간의 최댓값을 각각 구한다.

sticker[:-1]
sticker[1:]

마지막으로 두 결과 중 더 큰 값을 반환한다.

선형 스티커 DP

먼저 스티커가 원형이 아니라 일렬로 놓여 있다고 생각해보자.

dp[i]를 0번부터 i번 스티커까지 확인했을 때 얻을 수 있는 최댓값이라고 정의한다.

i번 스티커를 뜯지 않는다면 최댓값은 이전 위치의 결과와 같다.

dp[i - 1]

i번 스티커를 뜯는다면 바로 앞의 i - 1번 스티커는 뜯을 수 없다.

따라서 두 칸 전까지의 최댓값에 현재 스티커 값을 더한다.

dp[i - 2] + sticker[i]

두 경우 중 더 큰 값을 선택하면 다음 점화식이 만들어진다.

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

원형 구조 처리

원형 스티커에서 중요한 조건은 다음과 같다.

첫 번째 스티커와 마지막 스티커는 서로 인접한다.

따라서 두 스티커를 동시에 뜯을 수 없다.

모든 가능한 선택은 다음 두 경우 중 하나에 반드시 포함된다.

첫 번째 스티커를 고려하는 경우

첫 번째 스티커를 선택할 가능성을 열어두는 대신 마지막 스티커를 범위에서 제외한다.

sticker[:-1]

이 구간은 0번부터 N - 2번 스티커까지 포함한다.

마지막 스티커를 고려하는 경우

마지막 스티커를 선택할 가능성을 열어두는 대신 첫 번째 스티커를 범위에서 제외한다.

sticker[1:]

이 구간은 1번부터 N - 1번 스티커까지 포함한다.

두 경우를 각각 일렬 스티커 문제로 해결한 뒤 더 큰 값을 선택한다.

return max(
    get_max_sum(sticker[:-1]),
    get_max_sum(sticker[1:])
)

첫 번째 경우에서 반드시 첫 번째 스티커를 뜯어야 하는 것은 아니다.

마지막 스티커를 제외한 범위에서 최적의 선택을 구하는 것이므로 첫 번째 스티커를 뜯지 않는 경우도 자연스럽게 포함된다.

두 번째 경우도 마찬가지로 마지막 스티커를 반드시 뜯는 것은 아니다.

공간 최적화

점화식에서 현재 값을 계산할 때 필요한 값은 다음 두 개뿐이다.

dp[i - 2]
dp[i - 1]

따라서 전체 DP 배열을 만들 필요 없이 두 변수만 사용할 수 있다.

two_before = 0
one_before = 0

각 스티커 값을 확인하면서 현재 최댓값을 계산한다.

current = max(
    one_before,
    two_before + value
)

다음 반복을 위해 값을 한 칸씩 이동한다.

two_before, one_before = one_before, current

풀이 과정

1. 스티커가 한 장인 경우 처리

스티커가 한 장뿐이라면 해당 스티커를 뜯는 것이 최댓값이다.

if len(sticker) == 1:
    return sticker[0]

이 예외 처리를 하지 않으면 sticker[:-1]과 sticker[1:]가 빈 배열이 된다.

2. 선형 구간의 최댓값을 구하는 함수 작성

def get_max_sum(values):
    two_before = 0
    one_before = 0

    for value in values:
        current = max(
            one_before,
            two_before + value
        )

        two_before, one_before = one_before, current

    return one_before

3. 마지막 스티커를 제외한 경우 계산

exclude_last = get_max_sum(sticker[:-1])

첫 번째 스티커를 선택할 수 있도록 마지막 스티커를 제외한다.

4. 첫 번째 스티커를 제외한 경우 계산

exclude_first = get_max_sum(sticker[1:])

마지막 스티커를 선택할 수 있도록 첫 번째 스티커를 제외한다.

5. 두 결과 중 최댓값 반환

return max(exclude_last, exclude_first)

Python 코드

def solution(sticker):
    # 스티커가 한 장이면 해당 스티커를 선택한다.
    if len(sticker) == 1:
        return sticker[0]

    def get_max_sum(values):
        # dp[i - 2], dp[i - 1]
        two_before = 0
        one_before = 0

        for value in values:
            # 현재 스티커를 선택하지 않는 경우와
            # 현재 스티커를 선택하는 경우를 비교한다.
            current = max(
                one_before,
                two_before + value
            )

            two_before, one_before = one_before, current

        return one_before

    # 첫 번째 스티커를 고려하기 위해 마지막 스티커를 제외한다.
    exclude_last = get_max_sum(sticker[:-1])

    # 마지막 스티커를 고려하기 위해 첫 번째 스티커를 제외한다.
    exclude_first = get_max_sum(sticker[1:])

    return max(exclude_last, exclude_first)

코드 설명

한 장인 경우

if len(sticker) == 1:
    return sticker[0]

스티커가 한 장이라면 인접한 다른 스티커가 없으므로 그대로 선택하면 된다.

문제를 두 구간으로 나누기 전에 먼저 처리해야 하는 예외 상황이다.

두 칸 전 최댓값

two_before = 0

현재 스티커를 선택할 때 더할 수 있는 최댓값이다.

현재 위치의 바로 앞 스티커는 함께 선택할 수 없으므로 두 칸 전 결과를 사용한다.

한 칸 전 최댓값

one_before = 0

현재 스티커를 선택하지 않을 때 그대로 사용할 수 있는 이전 위치까지의 최댓값이다.

선택 여부 비교

current = max(
    one_before,
    two_before + value
)

첫 번째 값은 현재 스티커를 뜯지 않는 경우다.

두 번째 값은 현재 스티커를 뜯는 경우다.

두 경우 중 더 큰 값을 현재 위치까지의 최댓값으로 사용한다.

변수 이동

two_before, one_before = one_before, current

다음 스티커를 계산하기 위해 이전 결과들을 한 칸씩 이동한다.

파이썬의 다중 할당은 오른쪽 값들을 먼저 계산하므로 임시 변수를 만들지 않아도 된다.

두 구간으로 나누는 이유

sticker[:-1]
sticker[1:]

첫 번째와 마지막 스티커가 동시에 계산 범위에 들어가지 않도록 만든다.

이렇게 하면 각 범위는 원형이 아닌 일렬 구조가 되므로 일반적인 DP 점화식을 사용할 수 있다.

예시

다음 스티커 배열을 살펴보자.

sticker = [14, 6, 5, 11, 3, 9, 2, 10]

마지막 스티커를 제외한 경우

[14, 6, 5, 11, 3, 9, 2]

예를 들어 14, 11, 9를 선택할 수 있다.

14 + 11 + 9 = 34

첫 번째 스티커를 제외한 경우

[6, 5, 11, 3, 9, 2, 10]

6, 11, 9, 10을 선택할 수 있다.

6 + 11 + 9 + 10 = 36

두 경우 중 더 큰 값은 다음과 같다.

max(34, 36) = 36

따라서 정답은 36이다.

시간 복잡도

마지막 스티커를 제외한 구간과 첫 번째 스티커를 제외한 구간을 각각 한 번씩 순회한다.

O(n)

두 번 순회하더라도 상수 배만 증가하므로 전체 시간 복잡도는 O(n)이다.

n이 최대 100,000이어도 충분히 처리할 수 있다.

공간 복잡도

DP 계산 자체는 두 변수만 사용한다.

O(1)

다만 코드의 sticker[:-1], sticker[1:]는 파이썬에서 새로운 리스트를 만들기 때문에 슬라이싱에 O(n)의 추가 공간이 사용된다.

슬라이싱까지 포함한 실제 공간 복잡도는 다음과 같다.

O(n)

추가 공간을 완전히 O(1)로 줄이고 싶다면 배열을 복사하지 않고 시작 인덱스와 종료 인덱스를 함수에 전달할 수 있다.

슬라이싱 없이 구현하기

배열 복사를 피하려면 계산할 구간의 시작과 끝 인덱스를 전달한다.

def solution(sticker):
    if len(sticker) == 1:
        return sticker[0]

    def get_max_sum(start, end):
        two_before = 0
        one_before = 0

        for index in range(start, end):
            current = max(
                one_before,
                two_before + sticker[index]
            )

            two_before, one_before = one_before, current

        return one_before

    exclude_last = get_max_sum(0, len(sticker) - 1)
    exclude_first = get_max_sum(1, len(sticker))

    return max(exclude_last, exclude_first)

이 구현의 시간 복잡도와 공간 복잡도는 다음과 같다.

시간 복잡도: O(n)
공간 복잡도: O(1)

정리

이 문제는 원형 배열을 두 개의 선형 배열 문제로 나누어 해결하는 동적 계획법 문제다.

풀이 흐름은 다음과 같다.

스티커가 한 장이면 해당 값 반환
마지막 스티커를 제외한 구간의 최댓값 계산
첫 번째 스티커를 제외한 구간의 최댓값 계산
각 구간에서 현재 스티커 선택 여부를 DP로 비교
두 구간의 결과 중 최댓값 반환

첫 번째와 마지막 스티커를 동시에 선택할 수 없다는 원형 구조의 조건을 두 경우로 분리하는 것과, 선형 구간에서 dp[i - 1]과 dp[i - 2]만 사용해 값을 계산하는 것이 핵심이다.