[파이썬/Python] 백준 1181번: 단어 정렬

📌 문제 : 백준 1181번

---

📌 문제 탐색하기

N : 입력될 단어의 수 (1 ≤ N ≤ 20,000)
word : 알파벳 소문자로 이루어진 단어 (길이 ≤ 50)
words : 입력된 단어들이 저장될 리스트

정렬 조건
1. 길이 짧은 순
2. 길이 같으면 사전 순
+ 중복 단어는 1개만 남기고 삭제

N을 입력받고 N번 반복해서 단어들을 입력받아 리스트에 저장한다.
먼저 중복 단어를 제거하기 위해 set() 함수를 사용하고 다시 리스트로 바꿔준다.
sort() 함수를 통해 len(word)을 첫번째 기준으로 오름차순 정렬한 후, 2번째 기준으로 단어 자체를 기준으로 정렬한다.

가능한 시간복잡도

N개 입력 받기 → $O(N * 단어길이)$
set 함수 사용 후 list 함수 사용 → $O(N)$
sorted() 함수 사용 → $M(중복 제거 후 단어 수) * logM * (단어 길이)$

최악의 경우, N개의 단어가 모두 중복되지 않았고 단어 길이가 최대이다.
제한 시간 내에 계산 가능하므로 이 방법으로 문제를 해결한다.

알고리즘 선택

sorted() 함수로 정렬

---

📌 코드 설계하기

1. N 입력
2. for문으로 N개의 단어 입력
3. set 함수로 중복 제거
4. sort() 함수로 2가지 기준에 따라 정렬
5. 원하는 형식으로 출력
   
   

---

📌 정답 코드

import sys

input = sys.stdin.readline

# 1. N 입력
N = int(input())

# 2. for문으로 N개의 단어 입력
words = [str(input().rstrip()) for _ in range(N)]

# 3. set 함수로 중복 제거
no_overlap_words = list(set(words))

# 4. sort() 함수로 2가지 기준에 따라 정렬
sort_words = sorted(no_overlap_words, key=lambda x: (len(x), x))

# 5. 원하는 형식으로 출력
for word in sort_words:
    print(word)

• 결과