2469번: 사다리 타기

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

 

언어 : Kotlin

 

문제 설명 :

k명의 참가자들이 사다리 타기를 통하여 어떤 순서를 결정한다. 참가자들은 알파벳 대문자 첫 k개로 표현되며, 사다리 타기를 시작할 때의 순서는 아래 그림과 같이 항상 알파벳 순서대로이다. 

k=10 인 예를 들어 보자. 10명의 A, B, C, D, E, F, G, H, I, J 참가자들이 사다리 타기를 준비한다. 아래 그림은 10개의 세로 줄과 5개의 가로 줄을 가지고 있는 사다리의 한 예를 보여주고 있다.

 

이 사다리에서 점선은 가로 막대가 없음을, 굵은 가로 실선은 옆으로 건너갈 수 있는 가로 막대가 있음을 나타내고 있다.  

따라서 위에 제시된 사다리를 타면 그 최종 도달된 순서는 왼쪽으로부터 A, C, G, B, E, D, J, F, I, H 가 된다. 

사다리 타기는 세로 막대를 타고 내려오는 중에 가로막대를 만나면 그 쪽으로 옮겨 가면서 끝까지 내려가는 과정이다.  따라서 사다리 타기의 규칙 특성상 아래 그림과 같이 두 가로 막대가 직접 연결될 수는 없으므로 이 상황은 이 문제에서 고려할 필요가 없다.

 

우리는 하나의 가로 줄이 감추어진 사다리를 받아서 그 줄의 각 칸에 가로 막대를 적절히 넣어서 참가자들의 최종 순서가 원하는 순서대로 나오도록 만들려고 한다.  

입력에서 사다리의 전체 모양은 각 줄에 있는 가로 막대의 유무로 표현된다. 각 줄에서 가로 막대가 없는 경우에는 ‘*’(별)문자, 있을 경우에는 ‘-’(빼기) 문자로 표시된다. 그리고 감추어진 특정 가로 줄은 길이 k-1인 ‘?’ (물음표) 문자열로 표시되어 있다.   

 

입력 :

첫 줄에는 참가한 사람의 수 k가 나온다(3 ≤ k ≤ 26). 그 다음 줄에는 가로 막대가 놓일 전체 가로 줄의 수를 나타내는 n이 나온다(3 ≤ n ≤ 1,000). 그리고 세 번째 줄에는 사다리를 타고 난 후 결정된 참가자들의 최종 순서가 길이 k인 대문자 문자열로 들어온다.  

k와 n, 그리고 도착순서 문자열이 나타난 다음, 이어지는 n개의 줄에는 앞서 설명한 바와 같이 ‘*’와 ‘-’ 문자로 이루어진 길이 k-1인 문자열이 주어진다. 그 중 감추어진 가로 줄은 길이가 k-1인 ‘?’ 문자열로 표시되어 있다.

 

출력 :

입력 파일 세 번째 줄에서 지정한 도착순서가 해당 사다리에서 만들어질 수 있도록 감추어진 가로 줄을 구성해야 한다. 

여러분은 감추어진 가로 줄의 상태를 재구성하여 이를 ‘*’(별) 문자와 ‘-’(빼기) 문자로 구성된 길이 k-1인 문자열로 만들어 출력하면 된다.

그런데 어떤 경우에는 그 감추어진 가로 줄을 어떻게 구성해도 원하는 순서를 얻을 수 없는 경우도 있다.  이 경우에는  ‘x’(소문자 엑스)로 구성된 길이 k-1인 문자열을 출력해야 한다.

 

제한 사항 :

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

 

입출력 예 :

입력	출력
10 5 ACGBEDJFIH *-***-*** -*-****** ????????? -**-***-* **-*-*-*-	**-*-***-
11 5 CGBEDJFKIHA *-***-**** -*-******- ?????????? -**-***-*- **-*-*-*-*	xxxxxxxxxx

 

풀이 : 

참가 인원 수 k가 10일때, 인원 시작 배치는 "ABCDEFGHIJ"로 알파벳 순서대로이다.

가로 사다리 수 n이 5일때, 아래와 같이 나온다.

*	-	*	*	*	-	*	*	*
-	*	-	*	*	*	*	*	*
?	?	?	?	?	?	?	?	?
-	*	*	-	*	*	*	-	*
*	*	-	*	-	*	-	*	-

 

 

이것을 배치해보면 다음과 같이 보여진다.

 

 

1) start -> 0 -> 1 순으로 인원들의 배치가 바뀌고 Index 2가 ?이므로 멈춘다.

 

여기서 추가로 구할 수 있는 것은 역으로 거슬러 올라가는 것이다.

2) end -> 4 -> 3 순으로 인원들의 배치를 바꾸면 Index 2에서 다시 멈춘다.

 

1)은 최종적으로 다음과 같은 배치를 보일 것이다.

before  = C A D B E G F H I J

 

2)는 최종적으로 다음과 같은 배치를 보일 것이다.

after  = C A B D G E F H J I

 

 

이를 다시 배치해보면 다음과 같을 것이다.

0

1

2

3

4

5

6

7

8

1

C

A

D

B

E

G

F

H

I

J

2

|

?

|

?

|

?

|

?

|

?

|

?

|

?

|

?

|

?

|

3

C

A

B

D

G

E

F

H

J

I

 

before와 after를 순서대로 비교하여 같으면 '*' 다르면 swap해준 뒤, '-'를 써넣어주면 된다.

이를 풀어 써보면

 

before	after	ladder
C	C	*
A	A	*
D	B	-
B	B(D)	*
E	G	-
G	G(E)	*
F	F	*
H	H	*
I	J	-
J	J(I)	*

 

after의 괄호 안의 문자가 swap 전, 문자이다.

swap은 같지 않은 경우의 idx에 위치한 문자와 idx + 1의 문자를 바꿔주면 된다.

그러면 사다리게임에서 '-'로 건너가게 된 것과 같은 효과를 얻게 된다.

 

위 풀이를 코드로 작성하면 된다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

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

    val k = readLine().toInt()
    val n = readLine().toInt()

    val before = StringBuilder()
    repeat(k) {
        before.append('A' + it)
    }
    val after = StringBuilder(readLine())

    // start - ? - end
    var unknownIdx = -1
    val ladder = Array<String>(n) {
        readLine().apply { if (contains("?")) unknownIdx = it }
    }

    // start -> ?
    for (i in 0 until unknownIdx) {
        for (j in 0 until k - 1) {
            if (ladder[i][j] == '-') swap(j, before)
        }
    }

    // end -> ?
    for (i in n - 1 downTo unknownIdx) {
        for (j in 0 until k - 1) {
            if (ladder[i][j] == '-') swap(j, after)
        }
    }

    val result = StringBuilder()
    for (i in 0 until k - 1) {
        if (before[i] != after[i]) {
            swap(i, before)
            result.append('-')
        } else {
            result.append('*')
        }
    }

    bw.write(if (before.toString() == after.toString()) "$result" else "x".repeat(k - 1))
    bw.flush()
    bw.close()
}

fun swap(idx: Int, sb: StringBuilder) {
    sb[idx] = sb[idx + 1].also { sb[idx + 1] = sb[idx] }
}