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

사용 언어: Kotlin

 

문제

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

위 사진과 같은 숫자 자판이 있다.

특정 숫자 문자열을 타이핑할때, 타이핑하는데에 걸리는 최소 시간을 return한다.

왼손 엄지는 4, 오른손 엄지는 6에서 시작한다.

제자리에서 다시 누르는 것은 1초가 걸린다.

상하좌우 인접한 숫자로 이동해 누르는 것은 2초가 걸린다.

대각선 인접한 숫자로 이동해 누르는 것은 3초가 걸린다.

이외에는 위 규칙에 의한 최소 시간이 걸린다.

제한사항

같은 숫자 버튼에 두 손가락을 올려놓을 수 없다.

 

numbers = 타이핑해야하는 숫자 문자열

1 <= numbers <= 100,000

풀이

각 숫자의 이동시 시간을 정리하여 저장하였다.

 

이를 dp를 이용해 풀었다.

dp[i][L][R]은 문자열의 i번째 숫자를 타이핑할때 왼손가락의 위치 L, 오른손가락의 위치 R로 정의한다.

 

cost[a][b]는 a 손가락을 b로 옮기기 위한 시간이라고 하고,

직전에 다른 손이 누른 숫자를 N이라고 하면,

dp[i][L][R] = min(dp[i][L][N] + cost[L][N], dp[i][N][R])이다.

 

이때, 유의해야 할 건 왼손과 오른손이 같은 위치에 있게 되는 경우를 예외처리해야 한다.(문제 제한사항)

코드

val cost = arrayOf(
    intArrayOf(1,7,6,7,5,4,5,3,2,3,),
    intArrayOf(7,1,2,4,2,3,5,4,5,6,),
    intArrayOf(6,2,1,2,3,2,3,5,4,5,),
    intArrayOf(7,4,2,1,5,3,2,6,5,4,),
    intArrayOf(5,2,3,5,1,2,4,2,3,5,),
    intArrayOf(4,3,2,3,2,1,2,3,2,3,),
    intArrayOf(5,5,3,2,4,2,1,5,3,2,),
    intArrayOf(3,4,5,6,2,3,5,1,2,4,),
    intArrayOf(2,5,4,5,3,2,3,2,1,2,),
    intArrayOf(3,6,5,4,5,3,2,4,2,1,),
)

fun solution(numbers: String): Int {
    val memo = Array(numbers.length+1) { idx ->
        Array(10) {
            IntArray(10) { Int.MAX_VALUE }
        }
    }

    memo[0][4][6] = 0

    for(i in 1 .. numbers.length) {
        var target = numbers[i-1].digitToInt()
        for(l in 0..9) {
            for(r in 0..9) {
                if(memo[i-1][l][r] == Int.MAX_VALUE) continue
                if(target != r) memo[i][target][r] = min(memo[i][target][r], memo[i-1][l][r] + cost[l][target])
                if(target != l) memo[i][l][target] = min(memo[i][l][target], memo[i-1][l][r] + cost[r][target])
            }
        }
    }
    return memo.last().minOf { it.minOf { it } }
}