[백준/2469] 사다리 타기 (python)

Problem : https://www.acmicpc.net/problem/2469

2469번: 사다리 타기

 

Difficulty : Gold 5

 

Status : Solved

 

Time : 00:17:19

 

---

 

문제 설명

 

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

 

입력 예시

10
5
ACGBEDJFIH
*-***-***
-*-******
?????????
-**-***-*
**-*-*-*-

 

출력 예시

**-*-***-

 

---

 

풀이

 

구현 문제. 핵심은 두 가지다.

 

• '????????'열 직전과 직후의 문자열을 생성하여
• 직전 문자열이 직후 문자열로 바뀔 수 있도록 하는 사다리타기 문자열을 찾는 것

이 되겠다. 첫 번째 경우부터 생각해 보자.

문자열의 규칙은 꽤 간단하다. i번째 문자열이 '*'라면 그대로 진행, '-'라면 입력 문자열 [i], [i+1]의 위치를 바꾼다. 또한 사다리꼴 문자열에는 방향성이 없다. 즉 직전의 문자열은 초기 문자열을 '???????'줄이 나올 때까지 문자열 규칙에 따라 계속 변환하면 되며, 직후의 문자열은 나중 문자열을 역순으로 '???????'줄이 나올 때까지 문자열 규칙에 따라 변환한다.

 

 

두 번째 경우. 앞서 말했듯,  i번째 문자열이 '*'라면 그대로 진행, '-'라면 입력 문자열 [i], [i+1]의 위치를 바꾼다. 이를 바꾸어 생각하면, 직전 문자열과 직후 문자열을 비교하여 [i]번째와 [i+1]번째 문자열 위치가 서로 바뀌어 있으면 i번째 명령어는 '-'. 그렇지 않다면 '*'로 여긴다. 이렇게 생성된 문자열 명령어를 따라 직전 문자열을 바꿨을 때, 그 결과가 직후 문자열이라면 이는 옳은 명령어이니 그대로 출력한다. 만약 일치하지 않는다면 원하는 순서를 얻을 수 없는 경우이므로 'xxxxxxxx'를 출력한다.

 

• input_process : 문자열 명령어를 input으로 받고, 직전 문자열과 직후 문자열을 구하기 위한 명령어셋을 나눈다. '???????'이 기준이 되며, 직후 문자열을 생성하는 명령어 리스트는 뒤집어주어야 함을 명심하자.
• switch : 입력받은 문자열을 commands 순서대로 문자열 명령어를 받아 변환하는 함수이다.
• make_command : 직전 문자열과 직후 문자열을 입력받아, 이에 맞는 명령어를 생성하는 함수이다. 자세한 알고리즘 설명은 윗 문단에 기재되어 있다.
• solve : 메인함수.

 

 

풀이 코드

import sys
input = sys.stdin.readline

K = int(input())
N = int(input())

original = [ chr(x) for x in range(65, 65+K) ]
converted = list(input().strip())

def input_process() :
  flg = False
  original_commands, converted_commands = list(), list()

  for _ in range(N) :
    command = input().strip()
    if command[0] == '?' :
      flg = True
    elif flg :
      converted_commands.append(command)
    else :
      original_commands.append(command)

  converted_commands.reverse()
  
  return original_commands, converted_commands

def switch(lines, commands) :
  for command in commands :
    for i in range(K-1) :
      if command[i] == '-' :
        lines[i], lines[i+1] = lines[i+1], lines[i]

def make_command(original, converted) :
  result = ''
  for i in range(K-1) :
    if original[i] == converted[i+1] and original[i+1] == converted[i] :
      result += '-'
    else :
      result += '*'

  test = original.copy()
  switch(test, [result])

  return result if test == converted else 'x'*(K-1)

def solve() :
  original_commands, converted_commands = input_process()
  switch(original, original_commands)
  switch(converted, converted_commands)

  result = make_command(original, converted)
  print(result)

solve()

풀이 완료~