백준 13417번 Pseudo code

문제 링크

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

13417번: 카드 문자열

 

시간 제한 / 메모리 제한

1 초

256 MB

 

문제

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

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

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

 

입력

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

출력

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

예제 입력

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

예제 출력

KMU
ASDFG
AAABCBC

문제 풀이를 위해 생각한 것

1. 사전순으로 빠르다는 것은 아스키코드 혹은 ordinary 넘버 상에서 더 값이 작은 것을 뜻한다.
2. 놓인 카드는 항상 왼쪽부터 가져갈 수 있다.
3. 가져온 카드는 왼쪽, 오른쪽 둘 중 한 곳에 넣을 수 있다.
4. 중간에 삽입할 수는 없기에 가장 왼쪽에 사전 상 앞서는 문자를 삽입해야 한다.

 

사용한 자료구조

큐, 덱.

카드를 가져올 때는 왼쪽에서만 -> 큐

카드를 삽입할 때는 오른쪽 왼쪽 상관 없이 -> 덱

 

풀이 코드

t = 첫 입력값을 정수로
각 테스트케이스 t마다:
	n = 첫 입렧값을 정수로
	word = 문자열 split한 결과를 덱 자료구조 word에 저장
	res = 덱 자료구조 선언

	word의 길이 동안:
		ch = word.popleft()
		if res가 비어있으면:
			res.append(ch)
		elif res에 원소가 있으면:
			if ch가 res[0]보다 사전 상 앞서거나 같은 순서이면:
				res.appendleft(ch)
			elif ch가 res[0]보다 사전 상 뒷 순서이면:
				res.append(ch)

	print res를 문자열로

 

시간 복잡도 분석

O(N).

word 배열에서 pop한 원소를 res 배열에 append하는 과정은 O(1) * 2이며, 이를 N개의 원소 동안 반복.

따라서 계수를 제외하면 시간 복잡도는 O(N).

 

문제에서 중요한 부분

문제의 제약 조건 자체가 알고리즘을 그리디하게 설계해도 최적의 해를 찾을 수 있도록 설계되었고, 이를 알아내는 것이 문제를 빠르게 파악하고 풀어내는 데에 중요했다.