[프로그래머스] Swift - 숫자 타자 대회

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

프로그래머스

 

2024.01.06 기준 Level 3

 

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

 

아이디어

문제 조건

• 키패드 모양의 자판 존재
• 왼손은 4의 위치 오른손은 6의 위치에서 시작
• 가중치 존재
  • 제자리 입력은 가중치 1
  • 상하좌우 이동은 가중치 2
  • 대각선 이동은 가중치 3
• 주어진 numbers를 모두 입력할 때 가중치의 합의 최솟값인 경우를 리턴

 

우선 가중치가 존재하기 때문에 숫자 a 부터 b 까지의 최소 비용을 구해야 한다.(최단 거리 문제와 마찬가지)

 

즉, 0~9까지의 숫자에 대해 다른 숫자까지 움직이는데 드는 가중치의 최솟값을 미리 구해놓는 것이다.

 

최소비용을 구해야 하기 때문에 BFS를 통해 구한다. 0~9까지이기 때문에 이 작업에서의 소요 시간은 크지 않다.

 

이제 비용에 대한 데이터를 모두 구했다면 numbers를 입력할 때 소요되는 최소 가중치를 구해야 한다.

 

처음에는 그냥 DFS로 구현을 해봤는데 numbers의 길이기 100,000이라 시간 초과가 발생했다.

중복되는 연산이 많기 때문이다.

 

DP를 활용하여 시간 복잡도를 대폭 낮출 수 있다.

 

numbers의 인덱스를 i라고 했을 때

dp[i][왼손 위치][오른손 위치] = 가중치

형태로 3차원 배열 dp를 생성한다.

 

점화식으로 표현하면

dp[i][left][right] = min(가중치[left][i]+dp[i+1][i][right], 가중치[right][i]+dp[i+1][left][i]

이다.

 

즉, 숫자 a로 이동할 때 왼손을 움직인 경우와 오른 손을 움직인 경우의 각각의 가중치 중에서 더 작은 값을 dp 배열에 저장하는 것이다.

 

 

풀이

1. getPosition 함수

fileprivate func getPosition(num: Int) -> (Int, Int) {
    if num == 0 { return (3, 1) }
    let num = num-1
    return (num/3, num%3)
}

 

숫자 num의 2차원 배열 위치를 리턴하는 함수이다.

 

2. getMinimumWeights 함수

fileprivate func getMinimumWeights(from start: Int) -> [Int] {
    let board = [[1,2,3],[4,5,6],[7,8,9], [-1, 0, -1]]
    var result = Array(repeating: Int.max, count: 10)
    let dx = [0, 0, 1, -1, -1, -1, 1, 1]
    let dy = [-1, 1, 0, 0, 1, -1, -1, 1]
    let (startX, startY) = getPosition(num: start)
    
    var queue = [(Int, Int, Int)]() // (x, y, 가중치 합)
    
    queue.append((startX, startY, 0))
    
    while !queue.isEmpty {
        let first = queue.removeFirst()
        let x = first.0
        let y = first.1
        let weight = first.2
        let num = board[x][y]
        
        result[num] = min(result[num], weight)
        
        for i in dx.indices {
            let nextX = x + dx[i]
            let nextY = y + dy[i]
            
            if nextX >= 0 && nextX < 4 && nextY >= 0 && nextY < 3 {
                let nextNum = board[nextX][nextY]
                
                if nextNum != -1, result[nextNum] == Int.max {
                    let distance = abs(dx[i]) + abs(dy[i])
                    
                    if distance == 1 { // 상하좌우
                        queue.append((nextX, nextY, weight + 2))
                    } else { // 대각선
                        queue.append((nextX, nextY, weight + 3))
                    }
                }
            }
        }
    }
    
    result[start] = 1
    
    return result
}

 

BFS를 활용하여 각 노드까지 이동 비용을 배열에 담아 리턴하는 함수이다.

대각선도 이동해야 하기 때문에 dx, dy 배열의 크기를 8로 설정했다.

 

대각선으로 이동했는지 여부를 판단하기 위해 let distance = abs(dx[i]) + abs(dy[i]) 로 이동 거리를 구하고 이것이 2 이상이면 대각선 이동이라고 판단했다.

 

마지막에 result[start] = 1로 설정한 이유는 이동하지 않고 바로 숫자를 입력한 경우는 가중치가 1이라고 문제 조건에서 제시했기 때문이다.

 

큐에 처음 넣을 때는 가중치가 0으로 들어가야 다른 숫자로 이동할 때 1이 더 더해지는 문제를 방지할 수 있기 때문에 0으로 넣고 마지막에 1로 바꿔주는 방식을 사용한 것이다.

 

 

3. solution 함수

fileprivate func solution(_ numbers:String) -> Int {
    let numbers = Array(numbers).map { Int(String($0))! }
    var dict = [Int: [Int]]() // key: 출발 번호, value: index 번호까지 이동하는데 최소 비용 배열
    
    for i in 0...9 {
        let weights = getMinimumWeights(from: i)
        dict[i] = weights
    }
    
    var dp = Array(repeating: Array(repeating: Array(repeating: Int.max, count: 10), count: 10), count: numbers.count)
    let n = numbers.count

    func getMinTime(idx: Int, left: Int, right: Int) -> Int {
        if idx == n { return 0 }
        let num = numbers[idx]
        
        if dp[idx][left][right] == Int.max {
            var weightWhenLeftHandMove = Int.max
            var weightWhenRightHandMove = Int.max
            
            if right != num {
                // 왼손으로 누르기
                weightWhenLeftHandMove = dict[left]![num] + getMinTime(idx: idx + 1, left: num, right: right)
            }
            
            if left != num {
                // 오른손으로 누르기
                weightWhenRightHandMove = dict[right]![num] + getMinTime(idx: idx + 1, left: left, right: num)
            }
            
            dp[idx][left][right] = min(weightWhenLeftHandMove, weightWhenRightHandMove)
        }
        
        return dp[idx][left][right]
    }
    
    return getMinTime(idx: 0, left: 4, right: 6)
}

 

dp 배열을 만들고 재귀적으로 getMinTime 함수를 호출하여 dp 배월을 채워나갑니다.

 

 

 

 

마무리

두개의 문제가 합쳐진 느낌입니다.

각 숫자 위치에서 다른 숫자까지의 가중치 최솟값을 구해 놓고

DP 개념을 활용하여 주어진 numbers를 입려할 때 가중치 최솟값을 또 구해야 하는 문제였습니다.

두 번째 케이스에서 아이디어가 잘 떠오르지 않아 다른 사람들의 답변으로부터 힌트를 얻어서 구현했습니다.