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

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

프로그래머스

 

2023.07.13 기준 Level 3

 

알고리즘 공부용으로 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

처음에는 DFS를 사용하여 완전탐색으로 접근했습니다.

하지만 sticker의 배열이 길이가 최대 100,000이기 때문에 시간 초과가 발상했습니다.

 

따라서 모든 경우의 수를 전부 탐색하는 것이 아니라 DP를 활용하여 Bottom Up 방식으로 문제를 해결해 보고자 했습니다. (구글링 살짝...)

기본 점화식은 dp[i] = max(dp[i-1], dp[i-2] + sticker[i]) 입니다.

 

dp[i-1]은 한칸 이전의 위치에서의 sum의 최댓값을 의미합니다.

따라서 i번째 스티커를 뜯지 않을거라면 한칸 이전 위치에서의 최댓값을 유지한다는 의미입니다.

 

dp[i-2] + sticker[i]는 전전 위치에서의 sum의 최댓값에 현재 위치의 스티커에 적힌 숫자를 더한 값입니다.

현재 위치의 스티커를 뜯어냈을 때의 경우입니다.

스티커를 뜯어내면 좌우 스티커를 사용할 수 없기 때문에 현재 위치를 뜯어낸다면 i-1번째는 사용 불가능 하기 때문에 배제하고 2칸 전의 위치에서의 sum의 최댓값에 현재 위치 스티커의 숫자를 더하게 되는 방식입니다.

 

이 문제에서는 한가지 더 고려해야 할 상황이 있습니다.

스티커가 원형으로 연결되어 있기 때문에 0번째 인덱스의 스티커를 뜯으면 마지막 스티커를 사용할 수 없다는 점입니다.

따라서 dp를 구성할 때 두가지 경우의 수를 나누어 구현해야 합니다.

 

1. 첫 번째 스티커를 뜯는 경우 ➡️ 마지막 스티커가 찢어진다. ➡️ 마지막 스티커는 검사할 필요가 없어진다.
2. 첫 번째 스티커를 뜯지 않는 경우 ➡️ 마지막 스티커까지 검사해야 한다.

즉 dp 배열을 2개 만들어서 두가지 경우의 수에서의 최댓값을 다 구한뒤 그 중에서 더 큰 값을 정답으로 리턴하면 됩니다.

 

 

풀이

fileprivate func solution(_ sticker:[Int]) -> Int{
    if sticker.count == 1 || sticker.count == 2 {
        return sticker.max()!
    }
    
    var answer = 0
    
    var dp1 = Array(repeating: 0, count: sticker.count)
    var dp2 = Array(repeating: 0, count: sticker.count)
    
    // dp1에서는 첫번째 스티커를 뜯는다. -> 마지막 스티커가 찢어진다. -> 마지막 스티커는 검사할 필요가 사라진다.
    dp1[0] = sticker[0]
    dp1[1] = max(sticker[0], sticker[1])
    
    for i in 2..<(dp1.count-1) {
        dp1[i] = max(dp1[i-1], dp1[i-2]+sticker[i])
    }
    
    // dp2에서는 첫번째 스티커를 뜯지 않는다. -> 마지막 스티커를 검사할 필요가 생긴다.
    dp2[0] = 0
    dp2[1] = sticker[1]
    
    for i in 2..<dp2.count {
        dp2[i] = max(dp2[i-1], dp2[i-2]+sticker[i])
    }
    
    let maxOfDp1 = dp1[dp1.count-2]
    let maxOfDp2 = dp2[dp2.count-1]
    
    answer = max(maxOfDp1, maxOfDp2)

    return answer
}

sticker 배열의 크기가 1 또는 2인경우에는 스티커를 아무거나 하나 뜯으면 더 이상 뜯을 스티커가 사라지기 때문에 그냥 sticker 배열의 최댓값을 바로 리턴하도록 했습니다. (이 코드를 넣지 않으면 아래에 반복문의 범위에서 런타임 에러가 발생합니다.)

 

마무리

아직 DP를 떠올리는 것이 쉽지 않은 것 같습니다.

이 문제에서는 첫 번째 스티커를 뜯는 상황과 그렇지 않은 상황으로 총 2가지 경우를 나누어서 DP를 구성해야 했는데 이 아이디어를 생각하는 것도 쉽지 않았습니다.