태욱이는 모든 카드를 다 가져온 후에 자신의 앞에 놓인 카드를 순서대로 이어 붙여 카드 문자열을 만들려고 함
예를 들어 3장의 카드가 [M, K, U] 순으로 놓여있다면
태욱이는 먼저 가장 왼쪽에 있는 “M”이 적힌 카드를 가져와서 자신의 앞에 놓음
다음으로 남은 카드 중 가장 왼쪽에 있는 “K”가 적힌 카드를 가져와서 가장 왼쪽에 두고, 이어서 “U”가 적힌 카드를 가져와서 다시 가장 왼쪽에 두면 “UKM”이라는 문자열을 만들 수 있음
만약 “K”가 적힌 카드를 가져와서 가장 왼쪽에 두고, 이어서 “U”가 적힌 카드를 가져와서 가장 오른쪽에 두면 “KMU”라는 문자열을 만들 수 있음
이때, 태욱이가 만들 수 있는 문자열 중 사전 순으로 가장 빠른 문자열은 “KMU”
N장의 카드에 적혀있는 알파벳의 처음 순서가 주어질 때, 태욱이가 만들 수 있는 카드 문자열 중사전 순으로 가장 빠른 문자열을 출력
입력
입력은 T개의 테스트 데이터로 구성
첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어짐
각각의 테스트 케이스의 첫째 줄에 처음에 놓여있는 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어짐
두 번째 줄에는 N장의 카드에 적힌 알파벳의 초기 순서가 주어짐
가장 왼쪽에 있는 카드에 적혀있는 알파벳부터 순서대로 N개가 공백으로 구분되어 주어짐
모든 카드에는 한 개씩의 알파벳이 적혀있으며, 모두 대문자
출력
입력받은 데이터에 대해, 한 줄에 1개씩 태욱이가 만들 수 있는 문자열 중에서 사전 순으로 가장 빠른 문자열을 출력
시간 제한: 1초
메모리 제한: 256 MB
"""
입출력 예시)
3
3
M K U
5
A S D F G
7
B A C A B A C
-> KMU
ASDFG
AAABCBC
"""
## 의사코드 ##
# 가장 왼쪽에 있는 카드부터 가져옴 -> 큐(FIFO)
# from collections import deque
# 생성할 문자열 = ''
# 방금 뽑은 카드
# deque.popleft()
# 가져온 카드를 앞에서 뽑은 카드들의 가장 왼쪽 또는 가장 오른쪽에 놓음
# -> 방금 뽑은 카드와 지금까지 생성된 문자열의 크기 비교
# 사전 순으로 더 빠른 알파벳을 생성할 문자열에 추가
통과한 코드
from collections import deque
t = int(input())
for _ in range(t):
n = int(input())
cards = deque(input().split())
res = '' # 생성할 문자열
while cards:
# 가장 왼쪽에 있는 카드 가져오기
s = cards.popleft()
# 생성할 문자열이 비어있으면 s 추가 (첫 번째 카드인 경우)
if res == '':
res += s
# 두 번째 카드부터
else:
# 방금 뽑은 카드가 지금까지 생성된 문자열보다 사전 순에서 더 빠르거나 같은 경우, 가장 왼쪽에 추가
if s <= res:
res = s + res
# 방금 뽑은 카드가 지금까지 생성된 문자열보다 사전 순에서 더 늦는 경우, 가장 오른쪽에 추가
else:
res = res + s
print(res)
-> 가장 왼쪽에 있는 카드부터 가져와야 하므로 큐(deque) 사용, 방금 뽑은 카드와 지금까지 생성된 문자열의 크기를 비교해서 사전 순에서 더 빠르면 가장 왼쪽에, 늦으면 가장 오른쪽에 추가
문자열 더하기 순서
res = 'MU'
s = 'K'
# s를 res의 가장 왼쪽에 추가
print(s + res) # -> 'KMU'
# s를 res의 가장 오른쪽에 추가
print(res + s) # -> 'MUK'
