[baekjoon] 백준 13417번(파이썬): 카드 문자열

문제

13417번: 카드 문자열

- N장의 카드가 일렬로 놓여있다.

- 각 카드에는 알파벳이 하나씩 적혀있다.

- 태욱이는 가장 왼쪽에 있는 카드부터 차례대로 한 장씩 가져올 수 있다.

- 가장 처음에 가져온 카드는 자신의 앞에 놓는다.

- 그다음부터는 가져온 카드를 자신의 앞에 놓인 카드들의 가장 왼쪽, 또는 가장 오른쪽에 놓는다. 태욱이는 모든 카드를 다 가져온 후에 자신의 앞에 놓인 카드를 순서대로 이어 붙여 카드 문자열을 만들려고 한다.

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

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

-  테스트 케이스의 개수를 나타내는 자연수 T가 주어진다.

- 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 

- N장의 카드에 적힌 알파벳의 초기 순서가 주어진다.

- 가장 왼쪽에 있는 카드에 적혀있는 알파벳부터 순서대로 N개가 공백으로 구분되어 주어진다.

- 모든 카드에는 한 개씩의 알파벳이 적혀있으며, 모두 대문자이다. 

알고리즘

- 테스트 케이스의 개수를 입력받는다.

- 테스트 케이스만큼 반복하여 만들 수 있는 빠른 문자열을 만든다.

- 카드의 개수와 문자열을 입력받는다.

- 첫 번째 카드는 조건의 상관없이 리스트에 추가한다.

- 첫 번째 카드를 제외한 카드부터 마지막 카드까지 비교한다.

- 비교는 아스키코드 기준으로 하고 조건의 맞게 리스트에 추가한다.

- join 함수를 통해 결과값을 출력한다.

코드

import sys

t = int(sys.stdin.readline())

for _ in range(t):
    res = []
    n = int(sys.stdin.readline())
    c = sys.stdin.readline().split()

    # 첫 번째 카드는 조건의 상관없이 리스트에 추가한다.
    res.append(c[0])

    # 첫 번째 카드를 제외한 카드부터 마지막 카드까지 비교한다.
    for i in range(1, n):

        # 아스키코드로 비교한다.
        # 첫번째 카드의 아스키코드가 다음 카드의 아스키 코드보다 작으면 제일 뒤에 카드를 추가한다.
        if ord(res[0]) < ord(c[i]):
            res.append(c[i])

        # 반대로 첫번째 카드 아스키코드가 크면 인덱스 기준으로 0번째자리에 다음 카드를 추가한다.
        else:
            res.insert(0, c[i])
            
    # join 함수를 통해 리스트를 문자열로 바꿔 출력한다.
    print(''.join(res))

github

junjange/CodingTest