프로그래머스 - 대충 만든 자판(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

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

 

[문제 설명]

1. 키보드가 있다. 

2. 특정 버튼으로 만들 수 있는 문자 조합이 주어진다. 예를 들어, 1번 버튼을 누르면 만들 수 있는 문자 'ABCDE'가 있다면 1번 버튼을 1번 누르면 A, 2번 누르면 B, 3번 누르면 C, .. 5번 누르면 E.

3. 특정 문자를 최소한 눌러서 만들어라.

 

[접근 방법]

알파벳별 최소 버튼 수를 기록하면 된다.

예를 들어, 'CDEBA', 'DABEA'가 있다고 생각하자.

여기서 A를 만들기 위해서는 최소 몇 번 버튼을 눌러야 할까? 'CDEBA'를 기준으로 5번. 'DABEA'를 기준으로 2번.

즉, 최소 2번으로 A를 만들 수 있다.

'A' = 2

이런 식으로 모든 문자를 파악해서 최소 횟수를 기록하자.

 

모든 문자 배열의 문자들을 파악해야하므로 (문자 배열 크기) * (문자 개수) == keymap의 길이 * keymap 원소의 길이

결과값을 구하기 위해서는 targets의 길이 * targets 원소의 길이

총합은  (keymap.length) * (100) + (targets.length) * 100이 된다. 따라서, 최댓값은 2만.

따라서, 시간복잡도는 여유롭다.

 

[코드]

fun main() {
    val solutionObject = Solution()
    println(solutionObject.solution(arrayOf("ABCA"), arrayOf("AAAA")).sum().equals(4))
    println(solutionObject.solution(arrayOf("ABCD"), arrayOf("AAAA")).sum().equals(4))
    println(solutionObject.solution(arrayOf("ABCD"), arrayOf("ACAZ")).sum().equals(-1))
    println(solutionObject.solution(arrayOf("ABCD"), arrayOf("ACAZ")).sum().equals(4).not())
}

class Solution {
    fun solution(keymap: Array<String>, targets: Array<String>): IntArray {
        var costForChar = IntArray(26) {Int.MAX_VALUE}
        keymap.forEach { string ->
            setCostForChar(string, costForChar)
        }

        var sum = IntArray(targets.size)
        for (index in targets.indices) {
            val minClickCount = getMinClickCount(targets[index], costForChar)
            if (minClickCount == Int.MAX_VALUE) {
                sum[index] = -1
                continue
            }
            sum[index] = sum[index].plus(minClickCount)
        }

        return sum
    }

    fun setCostForChar(string: String, costForChar: IntArray) {
        string.forEachIndexed { index, it ->
            costForChar[it - 'A'] = costForChar[it - 'A'].coerceAtMost(index + 1)
        }
    }

    fun getMinClickCount(string: String, costForChar: IntArray): Int {
        var sum = 0
        string.forEach {
            if (costForChar[it - 'A'] == Int.MAX_VALUE) {
                return -1;
            }
            sum = sum.plus(costForChar[it - 'A'])
        }
        return sum
    }
}