[python/백준] 1181. 단어 정렬(S5)

📌 문제 탐색하기

👉 문제바로가기
N: 사용자로부터 입력받을 단어의 개수(문자열 자료형, 1<=N<=20,000)

N개의 단어를 입력받으면 배열에 저장하면 되겠네요. 저장 후에는 정렬을 시작합니다.

우선 sort()를 사용하여 사전 순으로 정렬해줍니다. 이후 길이순으로 정렬해야 하므로 sort()에서 key=len으로 한 번 더 정렬해줍니다.

*처음에는 길이 순으로 먼저 정렬 후 사전 순으로 정렬하려고 했으나.. 이렇게 하는 경우 길이순으로 정렬된 것이 의미가 없어집니다.

가능한 시간복잡도

sort함수만 사용하므로 시간복잡도는 O(NlogN)입니다.

알고리즘 선택

10814번 문제 해결에서도 언급했지만 파이썬에서 정렬하는 함수로 sort()와 sorted()가 있는데, 여기서는 기존 원본이 수정되어도 상관없으니 sort를 사용해도 무방합니다. 속도도 sort()가 더 빠르므로 사용하지 않을 이유가 없겠네요.

sort함수의 경우 시간복잡도 O(NlogN)중에서도 충분히 최적화가 잘 된 알고리즘이니, 걱정없이 사용해도 좋겠네요.

📌 코드 설계하기

1. 단어의 개수(N)를 사용자로부터 입력받는다.
2. N만큼 반복하면서 한 줄에 한 단어씩 입력받는다.
3. 리스트 요소의 중복을 제거한다.
4. 입력받은 단어를 sort()를 사용하여 사전 순으로 정렬한다.
5. sort함수에서 key=len을 사용하여 길이 순으로 정렬한다.
6. 정렬된 리스트 요소를 한 줄에 하나씩 출력한다.

📌 정답 코드

import sys

N = int(sys.stdin.readline())  # 입력받을 단어의 개수
word = [sys.stdin.readline().strip() for i in range(N)]  # 단어를 저장할 배열

# 중복제거
word = list(set(word))

# 사전순 정렬
word.sort()

# 길이순 정렬
word.sort(key=len)

for i in range(len(word)):
  print(word[i])