[백준/파이썬] 1181번 단어 정렬 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1181번 단어 정렬
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

단어들을 길이 오름차순으로 정렬하고, 길이가 같으면 사전순으로 정렬하는 문제입니다.

중복 단어는 한 번만 출력합니다.

코드

import sys
words = list(set([sys.stdin.readline() for _ in range(int(sys.stdin.readline()))]))


def merge_sort(p, r):
    if p < r:
        q = (p + r)//2
        merge_sort(p, q)
        merge_sort(q+1, r)
        merge(p, q, r)
        
def merge(p, q, r):
    i = p
    j = q+1
    len_fr = len(words[i]) if i <= q else 99
    len_bc = len(words[j]) if j <= r else 99
    tmp = []
    while len_fr+len_bc<198:
        if len_fr < len_bc:
            tmp.append(words[i])
            i += 1
            len_fr = len(words[i]) if i <= q else 99
        elif len_fr > len_bc:
            tmp.append(words[j])
            j += 1
            len_bc = len(words[j]) if j <= r else 99
        else:
            for k in range(len_fr):
                if ord(words[i][k]) < ord(words[j][k]):
                    tmp.append(words[i])
                    i += 1
                    len_fr = len(words[i]) if i <= q else 99
                    break
                if ord(words[i][k]) > ord(words[j][k]):
                    tmp.append(words[j])
                    j += 1
                    len_bc = len(words[j]) if j <= r else 99
                    break
    for i in range(p, r+1):
        words[i] = tmp[i-p]

merge_sort(0, len(words)-1)
print(''.join(words))

설명

set으로 중복을 제거한 뒤, 커스텀 병합 정렬로

• 1순위: 단어 길이
• 2순위: 사전순

기준 정렬을 수행하고 출력합니다.

---

• 백준 문제풀이 전체 목록 보기

---