13417 - 카드문자열 ☑️ (deque, Array)

https://www.acmicpc.net/problem/13417

13417번: 카드 문자열

문제

N장의 카드가 일렬로 놓여있다. 각 카드에는 알파벳이 하나씩 적혀있다. 태욱이는 가장 왼쪽에 있는 카드부터 차례대로 한 장씩 가져올 수 있다. 가장 처음에 가져온 카드는 자신의 앞에 놓는다. 그다음부터는 가져온 카드를 자신의 앞에 놓인 카드들의 가장 왼쪽, 또는 가장 오른쪽에 놓는다. 태욱이는 모든 카드를 다 가져온 후에 자신의 앞에 놓인 카드를 순서대로 이어 붙여 카드 문자열을 만들려고 한다.

예를 들어 3장의 카드가 [M, K, U] 순으로 놓여있다고 하자. 태욱이는 먼저 가장 왼쪽에 있는 “M”이 적힌 카드를 가져와서 자신의 앞에 놓는다. 다음으로 남은 카드 중 가장 왼쪽에 있는 “K”가 적힌 카드를 가져와서 가장 왼쪽에 두고, 이어서 “U”가 적힌 카드를 가져와서 다시 가장 왼쪽에 두면 “UKM”이라는 문자열을 만들 수 있다. 만약 “K”가 적힌 카드를 가져와서 가장 왼쪽에 두고, 이어서 “U”가 적힌 카드를 가져와서 가장 오른쪽에 두면 “KMU”라는 문자열을 만들 수 있다. 이때, 태욱이가 만들 수 있는 문자열 중 사전 순으로 가장 빠른 문자열은 “KMU”이다.

N장의 카드에 적혀있는 알파벳의 처음 순서가 주어질 때, 태욱이가 만들 수 있는 카드 문자열 중 사전 순으로 가장 빠른 문자열을 출력하는 프로그램을 작성하시오.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 처음에 놓여있는 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 두 번째 줄에는 N장의 카드에 적힌 알파벳의 초기 순서가 주어진다. 가장 왼쪽에 있는 카드에 적혀있는 알파벳부터 순서대로 N개가 공백으로 구분되어 주어진다. 모든 카드에는 한 개씩의 알파벳이 적혀있으며, 모두 대문자이다.

출력

출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 한 줄에 1개씩 태욱이가 만들 수 있는 문자열 중에서 사전 순으로 가장 빠른 문자열을 출력한다.

예제 입력 1

3
3
M K U
5
A S D F G
7
B A C A B A C

예제 출력 1

KMU
ASDFG
AAABCBC

💡 이 문제를 보고 내가 생각한 것들, 생각한 순서

카드 문자열 중 사전 순으로 가장 빠른 문자열을 출력해야하므로

처음에 입력되어 있는 문자와 비교해서 다음 입력되는 문자열이 더 빠르면 왼쪽에, 뒤이면 오른쪽에 둔다.

💡 어떤 자료구조를 택했고 그 이유는?

배열을 사용해서 맨뒤에 추가하거나, 앞에 추가한다.

append, insert 사용

💡 그 자료구조를 이용해서 구체적으로 문제를 해결하는 로직

N 테스트 케이스 입력받기

N 카드의 장수 입력 받기

각 문자열 입력 받기

리스트를 생성하고 첫번째 카드를 0번째에 추가한다.

리스트에 첫번째 카드와 비교해서 사전순으로 앞이면 앞에 추가하고 뒤면 뒤에 추가한다.

사전순으로 비교는 아스키코드나 부등호를 이용한다.

 

https://ye5ni.tistory.com/84

(1) 테스트 케이스 T개 입력받기

(2) T번 만큼 카드의 개수 N과 N장의 카드에 적힌 알파벳의 초기 순서 init 문자열을 리스트로 입력받기

(3) 카드를 재배치할 빈 리스트 arr 선언 후, 제일 먼저 가져와야 할 init[0] 값 추가하기

(5) init의 i번째 요소 값이 arr의 0번째 요소(제일 앞에 있는 값) 보다 작거나 같다면 arr의 맨 앞에 추가해주기

(6) 그게 아니라면 arr의 맨 뒤에 추가해주기

(7) (4)~(6)과정을 init의 길이만큼 반복한 후 출력 형식에 맞춰서 출력해주기!

T = int(input()) #테스트케이스 입력받기
 
for _ in range(T):#테스트케이스 길이만큼 반복
    N = int(input()) #문자열 갯수 입력받기
    init = list(input().split()) init에 받은문자열을 넣는다.
 
    arr = [] #빈배열을 만들고
    arr.append(init[0]) #배열의 맨뒤에 첫번째카드를 넣는다.
 
    for i in range(1, len(init)): #입력받은 문자를 1부터 검사한다.
        if init[i] <= arr[0]: #첫번쨰넣은 것보다 같거나 작으면 
            arr.insert(0, init[i]) # 맨앞에 추가한다.
        else:
            arr.append(init[i]) #크면 맨뒤에 넣는다.
 
    [ print(i, end='') for i in arr ] #arr을 출력
    print()

T = int(input())

for _ in range(T):
    N = int(input())
    init = list(input().split())

    arr = []
    arr.append(init[0])

    for i in range(1, len(init)):
        if init[i] <= arr[0]:
            arr.insert(0, init[i])
        else:
            arr.append(init[i])
    print(''.join(arr))#띄어쓰기없이 합쳐서 하나의 문자열로 바꿔줌

💡 문제에서 중요한 부분

문제 이해가 어려웠다 ㅠㅠ

[Python] 문자열(string) 사전 순으로 비교하기

: 정수의 값을 비교하듯이 부등호(<,>,<=,>=)를 사용해서 어떤 문자열이 사전 순으로 나열했을 때 더 앞에 와야 하는지 판별할 수 있다.

append는 요소를 배열의 끝에 추가하고, insert는 원하는위치 앞에 넣을수 있다.