[프로그래머스] Swift - 카운트 다운

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

프로그래머스

 

2023.09.26 기준 Level 3

 

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

 

아이디어

문제 조건

• 다트를 던진다.
• 싱글(x1), 더블(x2), 트리플(x3), 불(50) 획득 가능
• 다트를 적게 던져서 target에 도달해야 함
• target에 도달하는 방법이 여러개고 필요한 다트 수가 같다면 "싱글"과 "불"을 최대한 많이 던졌을 때를 채택
• target이 주어졌을 때 최선의 경우 던질 다트의 수와 싱글 또는 불의 횟수를 배열에 담아 리턴

우선, 문제에서는 다트를 맞춰서 얻은 점수를 Target에서 빼서 0을 만드는 방식으로 소개했지만 더 간편하게 생각하기 위해 처음부터 0으로 시작하여 다트를 맞춰서 얻은 점수를 더해 나가 Target에 도달하면 승리라고 간주했다. (둘 다 동일한 결과이다!)

 

먼저 싱글, 더블, 트리플, 불의 모든 경우의 수를 찾았을 때 1발의 다트로 얻을 수 있는 점수 어레이를 구한다.

1~20까지의 수,
1~20까지의 수에 2를 곱한 수,
1~20까지의 수에 3을 곱한 수,
50 (불)

이렇게 모든 수를 어레이에 넣고 중복 제거를 위해 Set으로 캐스팅 한뒤 오름차순으로 정렬하여 다시 어레이 형태로 저장한다.

어레이의 이름은 numbers라고 정했다.

이제 풀이를 위한 준비는 끝났다!

 

DP

target이 최대 100,000까지 가능하기 때문에 무작정 모든 경우의 수를 완전탐색하면 시간 초과가 발생할 것이 뻔했다.

 

이럴 때 고려해봐야 하는 풀이법이 DP이다.

DP(Dynamic Promgramming)을 사용하면 일반적으로 O(n)으로 풀이가 가능하다.

 

DP를 사용할 때는 점화식을 세우는 것이 핵심이다.

 

우선 DP의 대상 배열을 생성해야 한다.

var dp = Array(repeating: target, count: 100_000 + 1)

이렇게 dp 배열을 생성했다.

이 배열의 인덱스는 총 점수를 의미한다.

dp[index]는 총 index 만큼의 점수를 획득했을 때 던진 다트 개수의 최솟값이다.

 

numbers에 속한 값들은 1방의 다트로 얻을 수 있기 때문에 

dp[num] = 1 로 초기화 한다. (num은 numbers의 element)

 

점화식을 세우면 다음과 같다.

dp[i] = min(dp[i], dp[i-num] + 1), 여기서 num은 numbers 배열의 element

 

즉, dp[i] (i 점수를 만들기 위한 다트의 개수의 최솟값)을 기존 값과 i-num 점수를 만들기 위한 다트의 개수에 1을 더한 값 중에서 더 작은 값으로 업데이트 한다.

 

이때 num은 numbers 배열에 있는 숫자들이다. 왜냐하면 다트 1방으로 얻을 수 있는 수를 뺀 값(i-num)을 만들 때 필요한 다트의 최소 개수에 1개를 더하면 i 점수를 만들 수 있기 때문이다.

 

이제 반복문을 돌며 dp 배열을 채워나가면 된다.

 

이 문제에서는 dp[target]이 최소일 때 싱글 또는 불의 개수도 구해야 하기 때문에 이 값도 계속 트래킹해야 한다.

이를 위해 새로운 배열을 하나 생성하고 dp 배열을 업데이트 할 때 마다 이 배열 또한 같이 업데이트 해준다.

var singleOrBullCnt = Array(repeating: 0, count: 100_000 + 1)

singleOrBullCnt 로 배열의 이름을 붙였다.

 

 

 

풀이

1. makePossibleNumbers 함수 구현

// 1발의 다트를 던져서 얻을 수 있는 수를 오름차순으로 정렬해서 리턴
fileprivate func makePossibleNumbers() -> [Int] {
    var numbers = (1...20).map { $0 }
    
    (1...20).forEach { num in
        numbers.append(num * 2)
        numbers.append(num * 3)
    }
    
    numbers.append(50)
    
    return Set(numbers).sorted()
}

다트 1개를 던져서 얻을 수 있는 수를 오름차순으로 중복 제거하여 리턴하는 함수이다.

 

2. isSignleOrBull 함수 구현

fileprivate func isSingleOrBull(_ num: Int) -> Bool {
    return num <= 20 || num == 50
}

파라미터로 받아온 수가 single 또는 bull인지 판단하는 함수이다.

 

3. solution 함수 구현

fileprivate func solution(_ target:Int) -> [Int] {
    // 1
    var dp = Array(repeating: target, count: 100_000 + 1)  // index: 총 점수, dp[index]: 총 index 점수가 나왔을 때 던진 다트 개수의 최솟값
    var singleOrBullCnt = Array(repeating: 0, count: 100_000 + 1)    // singleOrBullCnt[index] 는 총 index 점수를 만들었을 때 싱글이나 불이 나온 횟수
    
    // 2
    if target <= 20 {
        return [1, 1]
    }
    
    // 3
    let numbers = makePossibleNumbers()
    
    // 4
    numbers.forEach {
        dp[$0] = 1
        if isSingleOrBull($0) {
            singleOrBullCnt[$0] = 1
        }
    }
    
    // 5
    for i in 21...target {
        for num in numbers {
        	// 6
            if i - num > 0 {
            	// 7
                let oneIfSingleOrBull = isSingleOrBull(num) ? 1 : 0
                
                if dp[i-num] + 1 < dp[i] {  // 8
                    dp[i] = dp[i-num] + 1
                    singleOrBullCnt[i] = singleOrBullCnt[i-num] + oneIfSingleOrBull
                } else if dp[i-num]+1 == dp[i] { // 9
                    singleOrBullCnt[i] = max(singleOrBullCnt[i], singleOrBullCnt[i-num] + oneIfSingleOrBull)
                }
            } else {
                break
            }
        }
    }

    // 10
    return [dp[target], singleOrBullCnt[target]]
}

주석에 달린 숫자 순서대로 설명

1. 앞서 설명한 dp와 singleOrBullCnt 배열을 생성한다. 각각 초기값은 target과 0으로 채웠다.
2. target이 20 이하면 1발의 다트로 완성시킬 수 있고 전부 single이기 때문에 [1,1]을 바로 리턴한다.
3. 다트 1발로 얻을 수 있는 점수 리스트를 생성한다. (오름차순 정렬 상태)
4. 3에서 얻은 배열을 순회하며 dp[$0]을 1로 채운다. 만약 싱글 또는 불이라면 singOrBullCnt[$0]도 1로 만들어준다.
5. 반복문을 돌며 dp를 채워 나간다.
6. numbers를 순회하며 i-num이 0보다 큰 경우에만 dp를 업데이트한다.
   • numbers를 순회하여 i-num을 구하는 이유는 numbers에 속한 값들은 다트 1회로 얻을 수 있는 점수들이고 따라서 i-num은 총 i점수에서 num을 뺀 점수를 의미한다.
   • i-num 점수를 만드는 다트 개수의 최솟값이 k개라면 i는 k+1개의 다트로 만들 수 있는 점수이다.
7. num이 싱글 또는 불이면 1을 아니면 0을 oneIfSingleOrBull에 저장한다.
8. dp[i-num] + 1 < dp[i] 라면 dp[i]를 업데이트 한다.
   • singleOrBullCnt 또한 업데이트 해준다.
9. dp[i-num] + 1 == dp[i] 인 상태는 기존에 구한 최솟값과 현재 탐색중인 최솟값이 같은 상태이다.
   • 문제 조건에 따라 이런 경우 싱글이나 불이 많을 때를 최선의 경우로 간주해야 한다.
   • 따라서 기존 싱글 또는 불의 개수와 현재 탐색 중인 경우의 싱글 또는 불의 개수 중 큰 값을 선택하여 업데이트한다.
10. dp[target]과 singleOrBullCnt[target]을 담아서 리턴한다.

 

 

 

 

마무리

DP를 사용하면 깔끔하게 풀리는 문제였다.

numbers.count가 42이기 때문에 Worst Case에서 42 * 100,000번의 연산이 필요했다. (통과 가능한 정도!)

numbers를 오름차순 정렬했고 i-num이 0보다 작아지는 경우에는 바로 break를 했기 때문에 실제로는 더 작은 연산 횟수로 동작하게 된다.

 

일반적인 DP문제에서 싱글과 불의 개수를 함께 카운팅해야 하기 때문에 살짝 더 어려워진 문제였던 것 같다!