[알고리즘][파이썬] 백준_1181_단어 정렬

https://www.acmicpc.net/problem/1181

1181번: 단어 정렬

N개의 알파벳 소문자 문자열을

길이가 짧은 것부터, 길이가 같으면 사전 순으로

정렬해야한다.

---

시간 초과

# 1차 시도(결과: 시간 초과)
import sys
N = int(sys.stdin.readline())

ipt = []
for _ in range(N):
    ipt.append(sys.stdin.readline().strip('\n')) # strip() 메서드 이용하여 '\n' 제거

ipt = list(set(ipt))
ipt.sort()

rst = []
for i in ipt:
    rst.append([len(i), i])
    rst.sort() # for 문 안에 sort 함수가 들어가 있어 불필요한 정렬이 반복되었음

for i in rst:
    print(i[1])

 

출력 결과에는 문제가 없었다.

위 코드에서 어떤 부분이 시간 복잡도를 높인 걸까?

set 함수?

2번 사용한 sort 함수?

3번 사용한 for 문?

set 함수는 중복된 문자열을 제거해야 하기 때문에 생략 할 수 없고,

for 문도 3개 모두 사용하지 않을 수가 없다!

두번째 사용한 sort 함수가 for 문 안에 위치해 있다.

불필요한 정렬이 반복되니

"시간 초과"가

발생한 것이다.

---

최종 제출 코드

# sort 함수 수정(결과: 맞았습니다!)
import sys
N = int(sys.stdin.readline())

ipt = []
for _ in range(N):
    ipt.append(sys.stdin.readline().strip('\n'))

ipt = list(set(ipt))
ipt.sort()

rst = []
for i in ipt:
    rst.append([len(i), i])

rst.sort() # for문 밖으로 sort함수를 빼냄

for i in rst:
    print(i[1])