백준 13019 A를 B로 Kotlin (그리디)

문제 출처 : https://www.acmicpc.net/problem/13019

13019번: A를 B로

문제

문자열 A와 B가 주어진다. 한 번 문자열을 바꾸는 것은 A의 한 글자를 골라서 문자열의 가장 처음으로 옮기는 것을 의미한다.

A를 B로 바꾸기 위해서 문자열을 바꿔야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, 둘째 줄에 B가 주어진다. 두 문자열의 길이는 같으며, 길이는 50을 넘지 않는다. 또, 알파벳 대문자로만 이루어져 있다.

출력

첫째 줄에 A를 B로 바꾸는 연산 횟수의 최솟값을 출력한다. A를 B로 바꿀 수 없을 때는 -1을 출력한다.

알고리즘 분류

• 그리디 알고리즘

풀이

그리디 문제이다.

우선 A와 B 문자열이 다른 경우는 -1이기 때문에 둘을 sort하고 값이 다르다면 -1을 출력하고 걸러준다.

나머지가 문제다.

우선 앞에 있는 문자는 연산을 실행하면 자연스레 뒤로 밀려난다.

ABC

CBA를 생각해 보면 B와C를 앞으로 보내면 되는데, 우리는 연산의 횟수가 필요하므로 B와C 무엇을 먼저 앞으로 보내야 하는지는 알 필요가 없다. 왜냐면 B와C를 앞으로 보내야 하는 것을 안다면 B와C의 순서는 항상 알아서 올바른 순서로 연산할 것이기 때문이다.

따라서 우리는 무엇을 앞으로 보내야 할지, 그 '무엇'의 개수만 파악하면 된다.

A의 마지막 인덱스부터, B의 마지막 인덱스부터 비교하자.

AIdx = A.length-1

BIdx = B.length-1

이제 두 문자들을 비교하면 되는데 AIdx의 값과 BIdx의 값이 같다면 BIdx는 하나 줄인다.

AIdx는 두 문자가 같든 다르든 무조건 하나 줄인다.

ABC의 C와 CBA의 A를 비교하면 둘이 다르기 때문에 C는 앞으로 보내야 할 문자이다. // AIdx--

그 다음 ABC의 B와 CBA의 A를 비교하면 둘이 다르기 때문에 B는 앞으로 보내야 할 문자이다. // AIdx--

마지막으로 ABC의 A와 CBA의 A를 비교하면 둘이 같기 때문에 A는 냅둔다. // AIdx-- BIdx--

따라서 B와 C를 앞으로 보내야 하기 때문에 정답은 2가 된다.

코드

val br = System.`in`.bufferedReader()

fun main() = with(System.out.bufferedWriter()) {
    //input
    val a = br.readLine()
    val b = br.readLine()
    //solve
    if (a.toCharArray().sorted() != b.toCharArray().sorted()) write("-1")
    else {
        var ap = a.length - 1
        var bp = b.length - 1
        var cnt = 0
        while (ap >= 0) {
            if (a[ap] == b[bp]) {
                bp--
            } else {
                cnt++
            }
            ap--
        }
        write("$cnt")
    }
    close()
}