[BOJ, Python] 1181번 : 단어 정렬

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

예제 입력 1

13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours

예제 출력 1

i
im
it
no
but
more
wait
wont
yours
cannot
hesitate

 

풀이1

처음에 버블정렬을 구현해서 풀었는데, 단어의 개수 N이 20,000까지 라서 시간 초과가 떴다.

N = int(input())
words = []

for _ in range(N):
    words.append(input())

# 중복 제거를 위해 set -> list 변환
words = list(set(words))

for i in range(len(words) - 1):
    for j in range(i + 1, len(words)):
        if len(words[i]) > len(words[j]):
            words[i], words[j] = words[j], words[i]

        elif len(words[i]) == len(words[j]):
            if words[i] > words[j]:
                words[i], words[j] = words[j], words[i]

for word in words:
    print(word)

버블 정렬에서 길이에 대해 우선 정렬했고, 단어의 길이가 같다면 사전순으로 정렬했다.

하지만 시간초과에 걸려서 보잘것 없는 나의 버블 정렬은 실패

 

풀이2

시간 초과를 잡기 위해 파이썬 내장 정렬함수를 사용했다.

 

sort나 soted 함수는 시간복잡도가 O(NlogN)인 퀵정렬을 사용하기 때문에 시간초과에 걸리지 않았다.

이 방식에서 핵심 idea는 단어와 단어의 길이를 tuple 자료형으로 묶어서 리스트에 append하는 것이다.

이 idea는 시간초과 해결을 위해 솔루션을 찾다가 발견했는데 좋은 idea인 것 같다.

N = int(input())
words = []

for _ in range(N):
    word = input()
    words.append((word, len(word)))

# 중복 제거를 위해 set -> list 변환
words = list(set(words))

# word[1](단어의 길이)를 1st key로 우선 정렬하고
# word[0](단어)를 2nd key로 그 다음 정렬한다.
words = sorted(words, reverse = False, key = lambda word : (word[1], word[0]))

for word in words:
    print(word[0])

 

해결!