<백준> A와 B 2(Gold 5)

[백준]

12919번: A와 B 2

[깃허브]

ForCodeKata/baekjoon 문제집/A와 B 2 at main · heesoo-park/ForCodeKata

제출결과

 

---

문제를 보자마자 이전에 풀어봤던 유형인 거를 깨달았다. (https://retry-thinksubox.tistory.com/214)

문제 지문이 똑같은 거 같아서 비교를 해봤는데 차이가 있었다.

그게 문제를 좀 어렵게 만들었던 거 같다.

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

- A와 B 2
문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.

뒤집는 걸 먼저하느냐 추가하는 걸 먼저하느냐의 차이였다.

 

이전에 풀었던 문제에서는 먼저 뒤집고 B를 추가했기 때문에 마지막 문자만 확인해서 문자열에서 빼는 식으로 진행을 했었다.

그런데 이번에는 반대였기 때문에 그 방식이 안 될거라고 짐작하고 더하는 방식으로 진행을 했다.

숫자제한도 50까지였기 때문에 될 거라고 생각했다.

하지만... 시간초과가 났다.

그 이유는 경우의 수가 2^50가지였고 이는 시간제한을 훌쩍 넘기 때문이다.

이걸 제대로 고려하지 않았던 것이 문제였다.

 

새롭게 시도한 것은 이전처럼 문자열에서 문자를 빼며 값을 구해나가는 거였다.

뒤에서만 빼는 게 안 되는 케이스라면 조건을 나눠서 앞에도 체크하면 된다는 것을 블로그를 보며 깨달았다.

A에 대한 건 동일하고 B에 대한 걸 뒤집어서 생각해보면 뒤에 B를 추가하고 문자열을 뒤집었다는 건 맨 앞에 B가 있다는 말과 같다.

그래서 조건을 맨 마지막이 A인 경우와 맨 앞이 B인 경우, 2가지를 두고 재귀함수를 구성했다.

// 첫 문자가 B인 경우
if (current[0] == 'B') {
    val temp = current.substring(1).reversed()
    solve(target, temp)
}

// 마지막 문자가 A인 경우
if (current.last() == 'A') {
    val temp = current.substring(0, current.length - 1)
    solve(target, temp)
}

 

이 문제를 풀면서 처음에 StringBuilder를 사용하려고 했지만 이 문제에서는 사용하기 너무 어렵다는 걸 느꼈다.

temp 변수에 담으려고 deleteAt을 하면 그게 잠시 빼는 것이 아니라 정말 StringBuilder에서 빠져버리는 것이기 때문에 의도한 로직이 이루어지지 않더라...

그래서 마지막에는 그냥 String으로 변경했다.

 

해당 방법으로 작성한 코드는 다음과 같다.

// 결과값 저장 변수
var result = 0

fun main() = with(System.`in`.bufferedReader()) {
    val s = readln()
    val t = readln()

    solve(s, t)
    println(result)
}

fun solve(target: String, current: String) {
    // 길이가 같고
    if (current.length == target.length) {
        // 같은 문자열일 때
        if (current == target) {
            result = 1
        }

        return
    }

    // 첫 문자가 B인 경우
    if (current[0] == 'B') {
        val temp = current.substring(1).reversed()
        solve(target, temp)
    }

    // 마지막 문자가 A인 경우
    if (current.last() == 'A') {
        val temp = current.substring(0, current.length - 1)
        solve(target, temp)
    }
}