[백준] 2469. 문자열_사다리타기 - Python

문제

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인 문자열을 출력해야 한다.

 

-----------------------------------------------------------------------------------------------------------------------------------

★ 시작하기 전에

길다 길어~~ 문제 참 길다~~

그래도 읽다보니 재미있을 것 같았다. 코드가 길어질 것 같았다.

중앙에 사다리를 어떻게 둘 것인가.

비어있는 사다리의 바로 위 직전의 배열 상태, 바로 직후의 배열 상태를 안다면, 모양을 결정할 수 있지 않을까.

??? 배열 이전까지를 left 배열에 두고

??? 배열 이후를 right 배열에 두고

left 에서 사다리를 하나씩 꺼내 처음상태(A,B,C,D,E,F,---)에서 변화시킨다.

right에서 사다리를 하나씩 꺼내 마지막상태(A,C,G,B,E,---)에서 변화시킨다.

 

???? 직전 직후의 상태를 알게 된다면, ???의 모양을 결정할 수 있다.

 

import sys

input = sys.stdin.readline

n = int(input())
m = int(input())
#마지막 모양과 처음 모양을 정해준다. 각 for 반복에 시작배열이 된다.
final = list(map(str, input().strip()))
start = sorted(final)

# left는 '??' 나오기 전까지의 사다리 모양을 넣어둔다.
# right는 '??' 나온 이후의 사다리 모양을 넣어둔다.
left = 0
right = []

for _ in range(m):
    ladder = list(map(str,input().strip()))
    
    # '??'이 나오면 현재까지의 right를 left에 넣고 right는 초기화
    # 분리하기 위한 방법이다.
    if ladder == ['?' for _ in range(n-1)]:
        left = right
        right = []
        continue
    right.append(ladder)

# 처음상태(ABCDE~~)에서 '??'직전 배열을 알기 위한 코드이다.
# 앞에서 부터 하나씩 빼서 '-'이면 양 알파뱃의 위치를 바꾸어준다.
while left:
    ladder = left.pop(0)
    for i in range(n-1):
        if ladder[i] == '-':
            start[i], start[i+1] = start[i+1], start[i] 

# 마지막상태에서 같은 방식으로 역순으로 해준다.
while right:
    ladder = right.pop()
    for j in range(n-1):
        if ladder[j] == '-':
            final[j], final[j+1] = final[j+1], final[j]
# '??'인 부분의 초기상태를 *로 해준 후
# 자리를 바꾸어 같은 값이면 '*'을 '-'로 바꾸어준다.
ans = ['*' for _ in range(n-1)]
for k in range(n-1):
    if start[k] == final[k+1] and start[k+1] == final[k]:
        ans[k] = '-'
        start[k], start[k+1] = start[k+1], start[k]
# 바꾼 start와 final이 같으면 성공!
# 아니면 x를 출력한다.
if start != final:
    ans = ['x' for _ in range(n-1)]
print(''.join(ans))

긴 문제지만 재미있는 문제였다.