10453번: 문자열 변환

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

 

언어 : Kotlin

 

문제 설명 :

좋은 문자열은 다음과 같이 정의된다.

ab 는 좋은 문자열이다.
만약 문자열 [S]가 좋은 문자열이라면, 오른쪽과 왼쪽 끝에 각각 a와 b를 추가한 문자열 a[S]b 또한 좋은 문자열이다.
만약 문자열 [S]와 [T]가 좋은 문자열이라면 이들을 붙여 쓴 [S][T] 또한 좋은 문자열이다.
어떤 두 좋은 문자열 A와 B가 주어진다. 문자열 A를 '인접한 두 문자를 서로 바꾸는' 연산을 통해 문자열 B로 바꾸려고 한다. 이때 필요한 연산의 수를 구하는 프로그램을 작성하시오. A를 B로 바꾸는 중에 나타나는 문자열도 모두 좋은 문자열이어야 한다.

예를 들어, A = aabbabab 이고 B = aaaabbbb라 해 보자. 그렇다면 다음과 같이 5번의 연산을 통해 A를 B로 변환할 수 있다.

aabbabab → aabbaabb → aabababb → aabaabbb → aaababbb → aaaabbbb

 

입력 :

첫 줄에 테스트 케이스의 수 T가 주어진다.

각각의 테스트 케이스마다, 한 줄에 문자열 A, B가 공백으로 분리되어 주어진다. 이때 A와 B는 좋은 문자열이며, 각각의 길이는 2 이상 100,000 이하이다.

 

출력 :

T줄에 걸쳐서, 각 테스트 케이스에서 주어진 문자열 A를 문자열 B로 변환할 때 필요한 연산의 수를 출력하시오.

만약 변환이 불가능한 경우 -1을 출력한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 256MB

 

입출력 예 :

입력	출력
2 aabbabab aaaabbbb aabbab abaabb	5 2

 

풀이 : 

a, b의 문자열 길이 체크 후 같다면 a와 b에서 'a'의 위치를 각각의 리스트에 기록한다.

위치 리스트의 크기를 비교하고 같다면 다음으로 넘어간다.

 

aPos와 bPos에서 비교를 해나간다.

abs(a 문자열에서의 첫번째 a 위치 - b 문자열에서의 첫번째 a의 위치)를 cnt에 더해준다.

만약 같은위치라면 1 - 1 = 0이므로 위치 변동이 없을 것이다.

다른 위치라면 예를들어

 

예시 1번을 기준으로 확인해보자.

aabbabab

aaaabbbb

보기 편하게 b를 _로 바꾼다.

 

aa__a_a_

aaaa____

이 경우, 첫번째, 두번째 a의 위치는 같으므로 생략한다.

 

세번째부터 달라지는데

a 문자열의 세번째 a의 위치는 5, b 문자열의 세번째 a의 위치는 3이다.

5 - 3 = 2

 

마찬가지로 네번째는 7 - 4 = 3이므로

2 + 3 = 5

 

총 5회 이동했다.

 

문제에서는 혼동을 주기위해 ba를 묶어서 이동시키지만 실상 ab 순서대로 한쌍을 무조건 이뤄야한다.

() <-- 이 괄호의 순서처럼.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.abs

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    repeat(readLine().toInt()) {
        var answer = -1
        val (a, b) = readLine().split(" ")

        answer += checkMovementNum(a, b)
        bw.write("$answer\n")
    }

    bw.flush()
    bw.close()
}

fun checkMovementNum(a: String, b: String): Int {
    if (a.length != b.length) return 0

    var cnt = 1
    val aPos = mutableListOf<Int>()
    val bPos = mutableListOf<Int>()

    for (i in a.indices) {
        if (a[i] == 'a') aPos.add(i)
        if (b[i] == 'a') bPos.add(i)
    }

    if (aPos.size != bPos.size) return 0

    for (i in aPos.indices) {
        cnt += abs(aPos[i] - bPos[i])
    }

    return cnt
}