프로그래머스 숫자 타자 대회 Kotlin (dp)

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/136797

프로그래머스

문제 설명

위와 같은 모양으로 배열된 숫자 자판이 있습니다. 숫자 타자 대회는 이 동일한 자판을 사용하여 숫자로만 이루어진 긴 문자열을 누가 가장 빠르게 타이핑하는지 겨루는 대회입니다.

대회에 참가하려는 민희는 두 엄지 손가락을 이용하여 타이핑을 합니다. 민희는 항상 왼손 엄지를 4 위에, 오른손 엄지를 6 위에 두고 타이핑을 시작합니다. 엄지 손가락을 움직여 다음 숫자를 누르는 데에는 일정 시간이 듭니다. 민희는 어떤 두 숫자를 연속으로 입력하는 시간 비용을 몇몇 가중치로 분류하였습니다.

• 이동하지 않고 제자리에서 다시 누르는 것은 가중치가 1입니다.
• 상하좌우로 인접한 숫자로 이동하여 누르는 것은 가중치가 2입니다.
• 대각선으로 인접한 숫자로 이동하여 누르는 것은 가중치가 3입니다.
• 같지 않고 인접하지 않은 숫자를 누를 때는 위 규칙에 따라 가중치 합이 최소가 되는 경로를 따릅니다.

예를 들어 1 위에 있던 손가락을 0 으로 이동하여 누르는 것은 2 + 2 + 3 = 7 만큼의 가중치를 갖습니다.
단, 숫자 자판은 버튼의 크기가 작기 때문에 같은 숫자 버튼 위에 동시에 두 엄지 손가락을 올려놓을 수 없습니다. 즉, 어떤 숫자를 눌러야 할 차례에 그 숫자 위에 올려져 있는 손가락이 있다면 반드시 그 손가락으로 눌러야 합니다.

숫자로 이루어진 문자열 numbers가 주어졌을 때 최소한의 시간으로 타이핑을 하는 경우의 가중치 합을 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ numbers의 길이 ≤ 100,000
  • numbers는 아라비아 숫자로만 이루어진 문자열입니다.

입출력 예 설명

입출력 예 #1
왼손 엄지로 17, 오른손 엄지로 56을 누르면 가중치 10으로 최소입니다.

입출력 예 #2
오른손 엄지로 5, 왼손 엄지로 123을 누르거나 오른손 엄지로 5, 왼손 엄지로 1, 오른손 엄지로 23을 누르면 가중치 8로 최소입니다.

풀이

10만개의 숫자를 왼손, 오른손으로 누를지 선택하는 경우의 수는 2^10만으로 완탐은 불가하다.

본인은 dp를 이용해 중복 탐색을 줄였다.

dp[idx][l][r] = 왼손이 l, 오른손이 r에 있을 때 idx부터 마지막 numbers의 키패드를 누르기까지의 최소 이동 거리

 

        if (idx >= numbers.length) return 0
        if (dp[idx][l][r] != INF) return dp[idx][l][r]

기저 조건은 다음과 같다.

더 이상 누를 키패드가 없으면 0을 반환, 이미 최솟값을 가지고 있는 경우 그 값을 반환

//right vs left 최솟값
if (next != r) {
//            moveLeft
    dp[idx][l][r] = dp[idx][l][r].coerceAtMost(solve(numbers, idx + 1, next, r) + edge[l][next])
}
if (next != l) {
    //moveRight
    dp[idx][l][r] = dp[idx][l][r].coerceAtMost(solve(numbers, idx + 1, l, next) + edge[r][next])
}
//idx번째 숫자를 l,r상태에서 시작해서 끝까지 눌렀을 떄 최솟값
return dp[idx][l][r]

next(다음 누를 키패드)가 r과 같다면 r로 누르면 그만이다. r과 next가 다른 경우 l을 움직여주자. 반대도 마찬가지이다.

이렇게 재귀 함수의 블럭에서 매번 dp[idx][l][r]을 초기화하면서 탑다운 방식으로 훑고 우리가 이미 알고 있는 값이 있으면 사용함으로써 중복을 줄이는 것이다.

 

edge는 하드코딩으로 만들어줬다. *과 #은 신경쓰지 않아도 된다. numbers는 숫자만 나온다고 하니..

처음엔 edge를 플로이드 와샬로 만들어줬다.

10*10*10으로 1000밖에 안 되는데 플로이드 와샬로 만들어주니까 edge는 잘 만들어지는데 19,20번 입력에서 런타임 에러가 발생하는 어이없는 일이 발생했다.

+O(1000)으로 신경쓰지 않았던 플로이드 와샬 때문에 런타임 에러.. 허

코드

const val INF = 987654321

class Solution {

    val dp = Array(100000) { Array(10) { IntArray(10) { INF } } }
    val edge = 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 {
        return solve(numbers, 0, 4, 6)
    }

    private fun solve(numbers: String, idx: Int, l: Int, r: Int): Int {
        if (idx >= numbers.length) return 0
        if (dp[idx][l][r] != INF) return dp[idx][l][r]
        val next = (numbers[idx] - '0')
        //right vs left 최솟값
        if (next != r) {
//            moveLeft
            dp[idx][l][r] = dp[idx][l][r].coerceAtMost(solve(numbers, idx + 1, next, r) + edge[l][next])
        }
        if (next != l) {
            //moveRight
            dp[idx][l][r] = dp[idx][l][r].coerceAtMost(solve(numbers, idx + 1, l, next) + edge[r][next])
        }
        //idx번째 숫자를 l,r상태에서 시작해서 끝까지 눌렀을 떄 최솟값
        return dp[idx][l][r]
    }
}