[백준] 1181번 파이썬

import sys

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if len(left[i]) < len(right[j]):
            result.append(left[i])
            i += 1
        elif len(left[i]) > len(right[j]):
            result.append(right[j])
            j += 1
        else:
            if left[i] < right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
    result += left[i:]
    result += right[j:]
    return result

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr)//2
    left = arr[:mid]
    right = arr[mid:]
    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left, right)

n = int(input().strip())
words = []
for i in range(n):
    word = sys.stdin.readline().strip()
    if word not in words:
        words.append(word)

sorted_words = merge_sort(words)

for word in sorted_words:
    print(word)

전형적인 병합 정렬을 이용해 문제를 풀었다.

merge_sort 함수에 의해 단어가 정렬된다. 길이가 1이거나 0이면 당연히 정렬 되었다고 간주하고 그대로 return한다. 그렇지 않다면 리스트를 반으로 나눠 left 리스트와 right 리스트를 만든 후 자신을 재귀적으로 호출한다. 그 후 merge함수에서 정렬된 후 합쳐서 하나의 배열로 완성된다.
merge함수는 i와 j를 사용하여 두 배열의 요소를 비교한다. left 리스트의 단어 길이가 right 리스트의 단어 길이보다 작으면 left 리스트의 단어가 result 리스트에 추가된다. 반대도 마찬가지이다. 단어 길이가 같으면 사전 순서대로 비교해 먼저 오는 단어를 result 리스트에 추가한다.