인기도:B(A,B,C), 성공률:보통(낮음,보통,높음), 레벨:2(1~4)
About ShellSort ¶
여틀 왕(King Yertle)은 그의 거북이 왕관을 재배치해서 가장 계급이 높은 귀족과 가장 가까운 측근들을 더 위쪽으로 올리고 싶어한다. 쌓여있는 거북이들의 순서를 바꾸는 방법은 거북이 한 마리가 원래 자기 위치에서 빠져 나와서 맨 위로 올라가서 자리를 잡는 방법 밖에 없다.
거북이 스택의 원래 순서와 새로 만들어져야 할 스택의 순서가 주어졌을 때 최소한의 이동 횟수만으로 원래 스택을 새로운 스택으로 재배치할 수 있는 순서를 찾아야 한다.
Input ¶
입력의 첫번째 줄에는 테스트 케이스의 개수를 나타내는 K라는 정수 하나만 들어있다. 각 테스트 케이스는 스택에 들어있는 거북이의 개수를 나타내는 n이라는 정수로 시작되며 그 밑으로 n개의 줄에 걸쳐서 거북이 스택의 원래 배치가 기술된다. 각 줄에는 거북이의 이름이 들어있으며 맨 윗 줄에는 스택 맨 위에 있는 거북이의 이름이 있고 위에서 아래로 순서대로 거북이의 이름이 나열된다. 각 거북이한테는 그 거북이만의 이름이 주어지며 각 이름은 80글자를 넘지 않는 문자열이고, 알파벳, 숫자, 스페이스 문자, 점('.')만 쓰인다. 그 밑으로는 n개의 줄에 걸쳐서 새로운 스택이 기술되며 여기에서도 위에 있는 거북이부터 아래있는 거북이 순으로 이름이 열거된다. 각 테스트 케이스는 정확하게 2n+1개의 줄로 구성된다. 거북이의 수(n)는 200 이하로 제한된다.
output ¶
각 테스트 케이스에 대해 한 줄에 하나씩의 거북이 이름이 출력되며 이 거북이 이름은 스택을 빠져 나와서 맨 위로 올라가는 거북이의 이름을 의미한다. 이 출력에 나와있는 순서대로 자기 자리를 빠져 나와서 맨 위로 올라가는 과정을 반복하면 원래의 스택이 새로운 스택으로 바뀌어야 하며 최소한의 이동 횟수로 작업을 끝낼 수 있어야 한다. 이 조건을 만족하는 이동 방법이 여러 가지 있으면 그 중 아무 것이나 출력해도 된다.
서로 다른 테스트 케이스 사이에는 빈 줄을 하나씩 출력한다.
Sample Input ¶
~cpp 2 3 Yertle Duke of Earl Sir Lancelot Duke of Earl Yertle Sir Lancelot 9 Yertle Duke of Earl Sir Lancelot Elizabeth Windsor Michael Eisner Richard M. Nixon Mr. Rogers Ford Perfect Mack Yertle Richard M. Nixon Sir Lancelot Duke of Earl Elizabeth Windsor Michael Eisner Mr. Rogers Ford Perfect Mack
