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인 '?' (물음표) 문자열로 표시되어 있다.

사다리 타기 timer 1s memory 64MB

사다리 타기 1s 64MB