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

문제 링크: https://www.acmicpc.net/problem/1181

문제

 

문자열을 정렬하고 중복을 제거하는 문제이다.

---

코드

n = int(input())

li = [input().strip() for _ in range(n)]

li = list(set(li))

li.sort(key=lambda x: (len(x), x))

print('\n'.join(li))

 

 

입력받은 문자열을 strip()으로 한 글자씩 리스트에 저장하고

set()으로 중복 제거

lambda를 써서 정렬 기준을 정한 후, sort 함수로 정렬

 

---

시간 복잡도

입력 부분: O(n$\times$m)    $\leftarrow$    m 은 각 단어의 평균 길이

set() 변환: O(n)

list() 변환: O(n)

정렬 과정: Python의 sort()는 Timesort 알고리즘을 사용하므로 O(k$\times$n log n)

문자열 비교: O(m)    $\leftarrow$    m 은 각 단어의 평균 길이

출력 부분: O(n$\times$m)    $\leftarrow$    m 은 각 단어의 평균 길이

 

$\therefore$ 총 시간 복잡도: O(m$\times$n log n)

---

성능 개선

•  sys.readline() 사용
  단어의 개수가 $1 \leq N \leq 20,000$로 20,000개의 입력을 받게되면 input()을 사용하여 입력 받는 것은 비효율적임
  파이썬의 input() 함수는 내부적으로 sys.stdin.readline()을 사용하지만 입력을 받을 때, 표준 입력을 읽고 개행 문자 (\n)을 제거하는 과정이 있어 많은 수의 입력을 받을 때 비효율적임

---

수정한 코드

import sys

n = int(sys.stdin.readline())

li = [sys.stdin.readline().strip() for _ in range(n)]

li = list(set(li))

li.sort(key=lambda x: (len(x), x))

print('\n'.join(li))