백준 1181번 단어 정렬

풀이 언어 : PYTHON

풀이 방법 : 퀵정렬

# 퀵 정렬 알고리즘
def quick_sort(arr):
    # 입력된 배열의 길이가 1 이하라면 정렬할 게 없으므로 리턴
    if len(arr) <= 1:
        return arr
    # 현재 배열 중앙 인덱스에 위치한 값
    pivot = arr[len(arr)//2]
    lesser_arr, greater_arr = [],[]
    # pivot보다 작은 것과 큰 것을 구분하여 따로 담는다
    for chr in arr:
        result = isBig(chr, pivot)
        if result == ">":
            greater_arr.append(chr)
        elif result == "<":
            lesser_arr.append(chr)
    
    # 이 과정을 반복하면 어느새 정렬 완료
    return quick_sort(lesser_arr) + [pivot] + quick_sort(greater_arr)

# 둘 중 뭐가 더 큰가를 판단
def isBig(a, b) :
    if len(a) > len(b):
        return ">"
    elif len(a) < len(b):
        return "<"
    else :
        if a > b :
            return ">"
        elif a < b:
            return "<"
        else :
            return "="

# 테스트 케이스 수 입력
T = int(input())
# 배열 입력
arr = []
for i in range(0,T):
    arr.append(input())
# 퀵정렬 실행
result_arr = quick_sort(arr)
# 결과 출력
for i in result_arr :
    print(i)

 

링크

1181번: 단어 정렬 (acmicpc.net)