문제 풀이
구현
before = 구해야 하는 줄을 통과하기 전의 순서
after = 구해야 하는 줄을 통과하면 나와야 하는 순서
unknownRow = 구해야 하는 줄의 인덱스
CharArray.swap(i, j) = CharArray에서 인덱스 i, j의 원소를 뒤집는 확장 함수
sb = 출력해야 하는 가려진 줄을 저장하는 StringBuilder
사다리에서 가려진 줄 전까지의 상황을 before에 반영해야 하는데 먼저 어느 줄이 가려졌는지는 칸을 확인해야 하므로 먼저 모든 줄 i, 모든 칸 j에 대해 사다리를 확인하기 시작함
현재 칸의 기호를 c에 저장하고 이 기호가 '-'라면 가로 막대가 있는 것이므로 before[i]와 before[i + 1]을 확장 함수를 이용해 뒤집어줌
만약 c가 '?'라면 가려진 줄을 찾은 것이므로 unknownRow에 인덱스를 대입하고 반복문 탈출
줄, 칸에 대한 이중 반복문이므로 unknownRow가 발견되었을 때 반복문을 둘 다 탈출해야 하므로 unknownRow의 초기값이 아닌 다른 값이 들어있을 때 줄에 대한 반복문도 탈출함
이 과정을 거치면 가려진 줄 전까지의 상황을 before에 반영한 것이고 이제 after에 원하는 최종 순서가 되기 위해 가려진 줄을 통과하면 어떤 상황이 되어야 하는지를 사다리의 맨 밑에서부터 역추적해야 함
사다리의 맨 밑줄 n - 1부터 unknownRow + 1까지 거꾸로 확인하면서 최종 순서가 저장된 after 배열의 값을 가로 막대가 있으면 뒤집음
그럼 이제 가려진 줄을 통과하기 전 상태 before에서 어떻게 바뀌어야 after의 상태로 될 수 있는지 원소를 하나하나 확인하며 뒤집어야 하는 칸에 가로 막대를 두면 됨
i를 0부터 k - 1까지 확인하며 before[i]와 after[i]가 같다면 그 칸에 가로 막대를 둘 필요가 없는 것이므로 sb에 '*'을 추가하고 그렇지 않고 before[i]와 before[i + 1]을 뒤집어야 after 배열과 같게 된다면 가로 막대가 필요한 것이므로 '-'를 sb에 추가함
만약 두 가지 경우가 아니라면 정상적인 사다리 한 줄에서는 원하는 상황으로 만들 수 없는 것이므로 sb에 저장되었던 모든 기호들을 지우고 불가능 하다는 뜻의 'x'를 k - 1개 추가함
이를 거치면 가려진 줄이 sb에 저장되거나 불가능 하다는 뜻의 문자열이 저장되어 있으므로 출력하면 정답
풀이 설명
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인 ‘?’ (물음표) 문자열로 표시되어 있다.
사다리 타기를 한 줄씩 생각해보면 가로 막대가 있으면 그 가로 막대에 연결된 두 참가자가 서로 뒤바뀐다는 점을 알 수 있다. 따라서 처음 상태는 알파벳 순서대로 정해져 있으므로 구해야 하는 특정 줄 전까지의 상황을 한 줄씩 가로 막대가 있을 때마다 참가자를 서로 바꿔주면 구할 수 있다.
그리고 특정 줄 이후부터는 최종적으로 결과로 나와야 하는 순서가 주어져있으므로 맨 마지막 줄부터 한 줄씩 밑에서 순서를 바꾸기 시작하면 특정 줄을 거치고 나면 특정 줄 전까지 구해놓은 상황에서 특정 줄을 지나면 어떻게 바뀌어야 원하는 순서로 나오는지를 구할 수 있다.
따라서 사다리 정보를 ladder 배열에 저장하고 먼저 특정 줄 전까지의 상황을 구하기 위해 before 배열에 알파벳 순서대로 참가자들을 나열하고 한 줄씩 확인하면서 가로 막대에 의해 변경되는 순서를 반영해 특정 줄을 통과하기 전 상황을 before에 저장해 놓는다.
그 이후에는 최종 순서를 after 배열에 저장해놓고 사다리의 맨 밑줄 부터 특정 줄 전까지 거꾸로 올라가면서 특정 줄을 지나면 어떤 순서로 바뀌어야 하는지를 after 배열에 저장한다.
그 이후에 before 배열과 after 배열을 비교하면서 구해야 하는 특정 줄에 어떤 칸에 가로 막대를 두어야 before 배열의 순서를 after 배열의 순서로 만들 수 있는지 확인하면서 특정 줄을 복원하면 된다.
이는 before 배열의 원소와 after 배열의 원소를 하나하나 확인하면서 같은 칸에 같은 원소가 있다면 그 칸에는 가로 막대가 필요하지 않은 것이므로 '*'를 저장하고, 만약 인접한 두 칸이 바뀌어야 after와 같아진다면 그 칸에 가로 막대를 놓아야 하므로 '-'를 저장하고 before 배열에서 이에 맞게 순서를 변경해준다.
배열의 원소를 확인해보다가 저 두 가지 경우가 아닌 경우가 나온다면 이는 한 줄을 거쳐서는 원하는 순서를 낼 수 없다는 것이므로 'x'를 k - 1개 출력하면 되고 그것이 아니라면 저장한대로 특정 줄에 들어가야 할 정보를 출력하면 정답이 된다.
소스 코드
fun main(){
val k = readln().toInt()
val n = readln().toInt()
val before = CharArray(k){'A' + it}
val after = readln().toCharArray()
val ladder = Array(n){readln().toCharArray()}
var unknownRow = -1
fun CharArray.swap(i: Int, j: Int){
val temp = this[i]
this[i] = this[j]
this[j] = temp
}
for(i in 0 until n){
for(j in 0 until k - 1){
val c = ladder[i][j]
if(c == '-'){
before.swap(j, j + 1)
}
if(c == '?'){
unknownRow = i
break
}
}
if(unknownRow != -1) break
}
for(i in n - 1 downTo unknownRow + 1){
for(j in 0 until k - 1){
if(ladder[i][j] == '-') after.swap(j, j + 1)
}
}
val sb = StringBuilder()
for(i in 0 until k - 1){
if(before[i] == after[i]){
sb.append('*')
} else if(before[i] == after[i + 1] && before[i + 1] == after[i]){
sb.append('-')
before.swap(i, i + 1)
} else {
sb.clear()
repeat(k - 1){
sb.append('x')
}
break
}
}
print(sb)
}