문제
알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
- 길이가 짧은 것부터
- 길이가 같으면 사전 순으로
단, 중복된 단어는 하나만 남기고 제거해야 한다.
입력
첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.
출력
조건에 따라 정렬하여 단어들을 출력한다.
정답 코드
import sys
input = sys.stdin.readline
n = int(input())
words = []
for _ in range(n):
words.append(input().strip())
set_wods = set(words)
words = list(set_wods)
words.sort()
words.sort(key=len)
for w in words:
print(w)코드 풀이
import sys
input = sys.stdin.readline
n = int(input())
words = []
for _ in range(n):
words.append(input().strip())sys.stdin.readline()는 문자열로 입력받기 때문에 시간초과가 발생하지 않는다. 해당 문제에서는 input()을 사용해도 문제가 없지만 앞으로 코딩테스트를 준비하면서 시간초과의 문제가 발생할 수 있기 때문에 그냥 입력을 받을 때는 습관을 들이기로 했다.
이 코드에서 단어들을 하나씩 입력받을 때, strip()을 해주는 이유는 sys.stdin.readline()이 '\n'과 같은 개행문자까지 같이 읽어들이기 때문에 이 개행문자 없이 입력받기 위함이다.
set_wods = set(words)
words = list(set_wods)문제에서 중복된 단어는 하나만 남기고 제거하라고 했기 때문에, set() 함수를 이용해서 유니크한 단어만 남기고, 이를 다시 리스트 형식으로 변환한다.
words.sort()
words.sort(key=len)이 문제를 풀면서 처음 안 것인데 sort() 함수가 정수 뿐만 아니라 문자열도 정렬을 해준다는 것이다. 기본으로 알파벳 순서대로 정렬되고, key=len을 설정하면 문자열의 길이 순으로 정렬해준다.
처음 이 문제를 보고, ord를 이용해서 유니코드 값으로 문제를 풀어야겠다고 생각했다.
문제 조건에서 길이가 짧은 것부터 정렬하고, 길이가 같으면 사전 순으로 정렬하라고 제시하고 있다. 그래서 먼저 입력 받은 단어들을 알파벳 순으로 정렬한 뒤, 길이 순으로 재정렬하여 출력하면 된다.
이렇게 코드를 작성했을 때 메모리는 37024KB, 시간은 68ms가 나왔다.
