1181) 단어정렬

📌 문제 탐색하기

• 정렬 조건
  1. 길이 오름차순 2. 사전 오름차순
• 중복된 단어는 제거!

가능한 시간복잡도

시간 제한 : 2초
1 ≤ N ≤ 20,000

입력 처리: O(N)
중복 제거: O(N) (set을 사용한 중복 제거)
정렬: O(N log N) (Timsort 정렬)
출력: O(N)
=> O(N log N) = 약 80,000만 => 적합

알고리즘 선택

파이썬의 내장 정렬 함수인 sort()는 Timsort 알고리즘을 사용한다.
Timsort는 합병 정렬과 삽입 정렬의 장점을 결합한 알고리즘으로, 최악의 경우 시간 복잡도는 *O(N log N)

📌 코드 설계하기

1. 문제의 input 받기
2. 중복 제거
   • set 활용
3. 조건에 맞게 정렬 (1. 길이 오름차순 2. 사전 오름차순)
   • 람다식 활용
4. 출력

📌 시도 회차 수정 사항 (Optional)

1회차

import sys

# 1. input 받기
N = int(sys.stdin.readline())
arr = []
for _ in range(N):
    arr.append(sys.stdin.readline())

# 2. 중복 제거
unique = list(set(arr)) 

# 3. 정렬
unique.sort(key=lambda x: (len(x), x))

# 4. 출력
for u in unique:
    print(u)
    
# print(*unique, sep="\n")
    

• sys.stdin.readline() 를 사용했더니 출력에 개행이 한 줄씩 더 들어가 있어서 출력 형식이 다르다고 떴다.
• sys.stdin.readline()는 입출력은 빠르지만, 줄바꿈 문자를 포함하여 출력이 다르게 나올 수 있다. -> strip()을 사용하여 공백, 개행문자 제거하거나 input() 사용하기!

📌 정답 코드

# 1. input 받기
N = int(input())
arr = []
for _ in range(N):
    arr.append(input())

# 2. 중복 제거
unique = list(set(arr)) 

# 3. 정렬
unique.sort(key=lambda x: (len(x), x))

# 4. 출력
print(*unique, sep="\n")