코딩테스트 연습 - 스티커 모으기(2)

문제풀이 아이디어

문제의 유형 자체는 DP에서 많이 본 문제입니다. i번째까지의 스티커를 떼었을 때의 최대값을 dp를 통해 0부터 구하고 마지막 스티커의 최댓값까지 구했을 때 그 값을 리턴하면 됩니다. i번째 스티커까지의 최댓값을 i번째 스티커를 떼는 경우와 떼지 않는 경우의 값 중에 최댓값을 구해서 리턴하면 되는 것이죠. 점화식으로 표현하면 아래와 같습니다.

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

하지만 이 경우에는 스티커가 원형이라는 점에 주목해야 합니다. 스티커가 일직선으로 되어 있다면 위와 같은 점화식으로 쉽게 풀 수 있지만 스티커가 원형이라면 첫 번째 스티커를 떼는 경우 마지막 스티커도 뗄 수 없습니다. dp에 저장되는 값의 최댓값만 저장이 될 뿐 어떤 스티커가 떼어졌는지는 저장되지 않습니다. 따라서 마지막 스티커를 점화식에 넣을 때 이 스티커를 뗄 수 있는지 없는지 모르게 되는 것이죠.

따라서 이 경우는 dp를 2개 사용합니다. 첫 번째 스티커를 무조건 떼는 경우와 첫 번째 스티커를 무조건 떼지 않는 경우입니다. 첫 번째 스티커를 무조건 떼는 경우는 마지막 스티커를 뗄 수 없습니다. 반대로 첫 번째 스티커를 무조건 떼지 않는 경우는 마지막 스티커를 떼거나 떼지 않을 수 있습니다.

이렇게 2가지 경우로 구분해서 dp를 수행하고 각각 dp의 마지막 값을 비교해서 최댓값을 구하면 되는 것입니다.

예외 처리

위 dp를 위해서는 스티커의 길이가 1, 2일 때의 예외처리를 해주어야 합니다. (index out of range 에러를 방지)

코드

func solution(_ sticker:[Int]) -> Int {
    let count = sticker.count

    // sticker의 길이가 2 이하일 때 index out of range를 방지하기 위한 guard문
    guard count > 2 else {
        if count == 1 {
            return sticker[0]
        } else {
            return max(sticker[0], sticker[1])
        }
    }
    
    // 0번 스티커를 떼는 경우와 떼지 않는 경우로 구분해서 dp를 2개 선언
    var dp = Array(repeating: Array(repeating: 0, count: count), count: 2)
    
    // 0번 스티커를 떼는 경우의 초기값 세팅
    dp[0][0] = sticker[0]
    dp[0][1] = sticker[0]
    // 0번 스티커를 떼지 않는 경우 초기값 세팅
    dp[1][1] = sticker[1]
    
    // 0번 스티커를 떼는 경우 마지막 스티커를 뗄 수 없으므로 (count-2)번 스티커까지만 고려
    for i in 2..<(count - 1) {
        dp[0][i] = max(dp[0][i - 1], dp[0][i - 2] + sticker[i])
    }
    
    // 0번 스티커를 떼지 않는 경우 마지막 스티커까지 고려
    for i in 2..<count {
        dp[1][i] = max(dp[1][i - 1], dp[1][i - 2] + sticker[i])
    }

		// 2가지 dp에서 구한 값 중에 최대값을 리턴
    return max(dp[0][count - 2], dp[1][count - 1])
}