[백준] 12904. A와 B (Kotlin)

문제

https://www.acmicpc.net/problem/12904

12904번: A와 B

 

풀이

0. 문제 해석

처음에는 재귀 방식으로 2가지 케이스에 대해 계속 탐색하도록 풀었는데

시간초과가 발생하였다.

 

그래서 모든 케이스를 탐색하는 것이 아닌 , 사다리타기를 할때 목적지에서 역순으로 탐색하는 것 처럼 해결하였다.

약간의 발상전환만 하면 쉽게 풀 수 있는 문제이다.

 

• 문자열의 뒤에 A를 추가한다.
• 문자열을 뒤집고 뒤에 B를 추가한다.

 

 

두 가지 경우를 S 가 아닌 T 의 관점에서 역으로 바라본다면

 

T의 맨 뒤 문자가 A라면 무조건 A를 추가하는 연산이 진행되었다는 뜻이고,

T의 맨 뒤 문자가 B라면 무조건 뒤집고 B를 추가하는 연산이 진행되었다는 뜻이다.

 

이 과정을 역으로 밟아 뒤의 문자를 하나씩 줄여가면서, 그 줄여간 문자열이 S라면 만들 수 있는 경우이고,

끝까지 줄였는데 못 만들 경우 만들 수 없는 경우이다.

 

1. 전체 코드

// [백준] 12904. A와 B (Kotlin)
import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val s = readLine()
    var t = readLine()

    // 역으로 탐색
    while (true){
        // 바꿀 수 있으면 1 출력
        if(t == s){
            println(1)
            return@with
        }

        // 더 이상 탐색할 수 없을 때
        if(t.length == 1){
            break
        }

        val last = t.length - 1

        // 마지막 문자가 A면 A뺌
        if(t[last] == 'A'){
            t = t.substring(0,last)
        }
        // 마지막 문자가 B면 B빼고 그 역순
        else if(t[last] == 'B'){
            t = (t.substring(0,last)).reversed()
        }
    }

    // 바꿀 수 없으면 0 출력
    println(0)
}