[알고리즘] 백준 1181번: 단어 정렬

 

import sys 
from collections import deque 

N = int(sys.stdin.readline().strip())

words =[]
for i in range(N):
    word = sys.stdin.readline().strip()
    if word not in words:
        words.append(word)
words_buckets =[deque() for i in range(0,50)]
while words: 
    word =words.pop()
    words_buckets[len(word)-1].append(word)
words_buckets = [sorted(x) for x in words_buckets]
words =deque(words)

for buckets in words_buckets:
    while buckets:
        buckets =deque(buckets)
        words.append(buckets.popleft())
for word in words:
    print(word)

N개의 단어를 입력으로 받고 길이가 짧은 것을 앞에, 길이가 같다면 사전 순으로 배열함 

최대 50개까지 나오므로 처음에는 input을 받으면 길이에 따라 다른 칸에 집어넣어줌(1)

그리고 각각에 칸에 대해 정렬하고(2) 앞에서부터 꺼내면 끝

 

시간이 걸릴만한 부분은 (1)과 (2)인데 1은 radix sort를 응용한거라 n이었을거고 

(2)는 sorted 함수를 사용해서 nlogn이라 결론은 nlogn이었을것