[백준] 2469 - 사다리 타기 / Python / 골드 5

🚩문제 주소

문제 설명

---

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	출력 1
10	**-*-***-
5
ACGBEDJFIH
*-***-***
-*-******
?????????
-**-***-*
**-*-*-*-

입력 2	출력 2
11	xxxxxxxxxx
5
CGBEDJFKIHA
*-***-****
-*-******-
?????????
-**-***-*-
**-*-*-*-*

📄풀이

---

시작지점부터 ?를 만나기 전까지의 사다리와 도착지점부터 ?를 만나기 전까지의 사다리로 나눠줍니다.
두 사다리 배열을 비교하여 시작사다리[i]=도착사다리[i]라면 정답배열에 *를 추가하고, 시작사다리[i]=도착사다리[i+1]라면 -를 추가합니다.
이 경우가 아니라면 x를 k-1만큼 만든 후 추가합니다.
정답배열을 문자열로 합친 후 출력합니다.

👨‍💻코드

---

k = int(input())
n = int(input())
end = list(input())
start = sorted(end)
ladder = [list(input()) for _ in range(n)]
ladderS = []
ladderE = []
#?를 기준으로 사다리 나누기
for i in range(len(ladder)):
  if ladder[i][0] == '?':
    ladderS = ladder[:i]
    ladderE = ladder[i+1:]
    break
# ????만나기 전까지 사디리 타고 내려오기
for lad in ladderS:
  for i in range(k-1):
    if lad[i] == "-":
      start[i],start[i+1] = start[i+1],start[i]
# 도착 지점에서 ????만나기 전까지 사다리 타고 내려오기
ladderE.reverse()
for lad in ladderE:
  for i in range(k-1):
    if lad[i] == "-":
      end[i],end[i+1] = end[i+1],end[i]
# 두 배열 비교해서 사다리 만들기
answer = []
for i in range(len(start)-1):
  if start[i]==end[i]:
    answer.append("*")
  else:
    if start[i]==end[i+1]:
      answer.append("-")
    elif i!=0 and start[i]==end[i-1]:
      answer.append("*")
    else:
      answer = ['x' for _ in range(k-1)]
      break
#정답
print(''.join(answer))