1. 오늘의 문제
오늘 문제도 간단한 그리디 알고리즘이다.
딴짓 하면서 풀었는데, 다 풀기까지 20분정도 걸렸으니 엄청 쉬운편이다.
문제
N장의 카드가 일렬로 놓여있다. 각 카드에는 알파벳이 하나씩 적혀있다. 태욱이는 가장 왼쪽에 있는 카드부터 차례대로 한 장씩 가져올 수 있다. 가장 처음에 가져온 카드는 자신의 앞에 놓는다. 그다음부터는 가져온 카드를 자신의 앞에 놓인 카드들의 가장 왼쪽, 또는 가장 오른쪽에 놓는다. 태욱이는 모든 카드를 다 가져온 후에 자신의 앞에 놓인 카드를 순서대로 이어 붙여 카드 문자열을 만들려고 한다.
예를 들어 3장의 카드가 [M, K, U] 순으로 놓여있다고 하자. 태욱이는 먼저 가장 왼쪽에 있는 “M”이 적힌 카드를 가져와서 자신의 앞에 놓는다. 다음으로 남은 카드 중 가장 왼쪽에 있는 “K”가 적힌 카드를 가져와서 가장 왼쪽에 두고, 이어서 “U”가 적힌 카드를 가져와서 다시 가장 왼쪽에 두면 “UKM”이라는 문자열을 만들 수 있다. 만약 “K”가 적힌 카드를 가져와서 가장 왼쪽에 두고, 이어서 “U”가 적힌 카드를 가져와서 가장 오른쪽에 두면 “KMU”라는 문자열을 만들 수 있다. 이때, 태욱이가 만들 수 있는 문자열 중 사전 순으로 가장 빠른 문자열은 “KMU”이다.
N장의 카드에 적혀있는 알파벳의 처음 순서가 주어질 때, 태욱이가 만들 수 있는 카드 문자열 중 사전 순으로 가장 빠른 문자열을 출력하는 프로그램을 작성하시오.
입력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 처음에 놓여있는 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 두 번째 줄에는 N장의 카드에 적힌 알파벳의 초기 순서가 주어진다. 가장 왼쪽에 있는 카드에 적혀있는 알파벳부터 순서대로 N개가 공백으로 구분되어 주어진다. 모든 카드에는 한 개씩의 알파벳이 적혀있으며, 모두 대문자이다.
2. 원리
카드는 순서대로 나와야 하니 deque를 이용해서 queue를 구현하면 된다.
그리고 나온 카드는 앞이나 뒤에 추가해야 한다.
그러므로 맨 앞장에 있는 카드와 현재 뽑은 카드를 아스키 코드상에서 비교한 뒤, 제일 앞의 카드와 같거나 작으면 앞에 추가하고 이외의 경우에는 제일 뒤에 추가하면 된다.
파이썬은 문자열의 합을 구해주니 간단하게 풀린다.
3. 코드
from collections import deque
from sys import stdin
put = stdin.readline
# 받아야 카드의 총 집계
wordsNum = int(put())
for _ in range(wordsNum):
# 카드길이를 받은 뒤 각 단어를 deque에 집어넣는다.
wordsLength = int(put())
words = deque(map(str, input().split()))
result = ""
for i, _ in enumerate(range(wordsLength)):
# 카드를 꺼낸다. 첫번째 카드는 없으므로 결과값으로 치환한다.
word = words.popleft()
if i ==0:
result = word
continue
# 아스키코드 상에서 문자열의 숫자가 크면 뒤쪽에, 작거나 같으면 앞에 추가한다.
if ord(result[0]) < ord(word):
result = result + word
else:
result = word + result
print(result)
4. 느낀점
시간이 있을지 모르겠지만 문제가 쉬울 경우에는 챌린저 문제도 풀어봐야겠다.
스스로 구하지 않으면 아무것도 되지 않는 것 같다.
그리고 오늘부터 next에서 dashboard 예제를 제작하기 시작했다.
기존에 있던 예제를 활용해서 해보고 싶었는데 쉽지 않았다.
이럴 때마다 대학교 때 철학과 교수님이 했던 말이 생각난다.
기존의 것을 무너뜨리지 않으면 새로운 것을 만들수 없다.
이번 기회에 mySQL, Mongodb에서 예제이 있는 postgreSQL로 갈아타보아야 겠다.
