백준 1181 단어정렬 파이썬 풀이

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

1181번: 단어 정렬

 

문제 이해

 

여러 단어들이 입력된다. 단어를 길이 순서로 출력하되 만약 같다면 사전 순으로 출력하면 된다.

단어의 개수는 최대 20000개까지 했으니 O(n^2)로 풀 경우 시간 초과가 뜰 수도 있겠다는 생각을 갖고 접근했다. 

 

접근법

어떻게 풀어야할지 감이 안와서 일단 완전탐색으로 구현해보기로 했다.

문자열의 길이를 측정하고 그 길이에 따라 정렬하는 방식이다.

 

코드1(완전탐색)

import sys

n = int(sys.stdin.readline())
answer = list(set(sys.stdin.readline().strip() for _ in range(n)))

for i in range(len(answer)) :
    min_index = i
    for j in range(i + 1, len(answer)) :
        if len(answer[j]) < len(answer[min_index]) or (len(answer[j]) == len(answer[min_index]) and answer[j] < answer[min_index]):
            min_index = j
    answer[i], answer[min_index] = answer[min_index], answer[i]
    
for word in answer :
    print(word)

 

 

완전 탐색으로 풀었기 때문에 당연히 시간 초과가 떴다. O(n^2)으로 풀었을때 절대 풀 수 없을것이다. 그렇다면 더 나은 알고리즘을 생각해야 했다.

 

코드2

import sys

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

for _ in range(n):
    answer.add(sys.stdin.readline().strip())

answer = list(answer)
answer.sort()
answer.sort(key=len)
for word in answer :
    print(word)

 

중복 단어를 없애기 위해 set 자료구조를 사용했고 리스트로 변환 후 렬을 길이 기준으로 해주었다. 정렬 알고리즘의 시간 복잡도는 O(nlogn)이다. 이 코드는 이전에 시간초과 코드와 다르게 시간 초과가 뜨지 않을 것이라 생각해서 떠올린 코드이다.