[BOJ/python] 1413: 시리얼 번호

문제

✔️ silver 3

문자열
정렬

문제 흐름

문제의 정렬에는 세가지 기준이 있다.

1. 길이가 짧을 경우 앞 순서로 정렬한다.
2. 포함된 숫자의 합이 작은 경우 앞 순서로 정렬한다.
3. 위 두 경우가 일치할 경우 사전순 정렬을 따른다.

물론 python에는 정렬을 위한 내장 함수가 있고, 이의 정렬 기준을 커스텀할 수 있다.
정렬을 구현하는 것은 오랜만이기 때문에 머지소트를 이용해 직접 구현하기로 했다.

머지소트는 분할 -> 병합 단계를 거쳐야하는데, 입력 하나하나를 이미 분할된 상태로 보고 진행했다.
custom_compare는 sn1과 sn2를 입력받아 둘을 비교해 정렬된 순서로 반환한다.
merge_part는 sn을 입력받아 custom_compare를 이용해 둘을 앞부터 비교해 정렬된 순서로 병합하여 반환한다.
merge_sort는 전체적인 소트 과정 진행부분으로 문제의 input인 sn을 입력받아 merge_part를 이용해 부분부분을 병합하는 과정을 진행하고, 최종적으로 정렬된 리스트를 반환한다.

앞서 언급했던 기존의 내장 함수의 정렬 기준을 커스텀하여 해결하는 방법은 링크에서 확인할 수 있다.
python 내장 정렬 함수는 가장 효율적인 tim sort를 사용하기 때문에, 가장 효율적이고 간단한 방법일 거라고 생각은 했지만 정말 짧고 간결한 코드라 놀랐다.

코드

# 시리얼 번호

import sys

# 길이 -> 짧은것 부터
# 숫자 자릿수합 -> 작은것 부터
# 사전순 (숫자 -> 알파벳)

# N ≤ 50 
# 시리얼 번호 최대 길이 = 50

# merge sort
def custom_compare(sn1: str, sn2: str):
    if len(sn1) < len(sn2):
        return (sn1, sn2)
    elif len(sn1) > len(sn2):
        return (sn2, sn1)
    else:
        sum_sn = [0, 0]
        for i, sn in [(0, sn1), (1, sn2)]:
            for x in sn:
                try:
                    sum_sn[i] += int(x)
                except:
                    sum_sn[i] += 0
        if sum_sn[0] < sum_sn[1]:
            return (sn1, sn2)
        elif sum_sn[0] > sum_sn[1]:
            return (sn2, sn1)
        else:
            if sn1 < sn2:
                return (sn1, sn2)
            elif sn1 > sn2:
                return (sn2, sn1)
            else:
                return 0 # 잘못된 입력

def merge_part(part1: list, part2: list):
    result = []
    i, j = 0, 0
    while i < len(part1) or j < len(part2):
        if i >= len(part1):
            result.append(part2[j])
            j += 1
            continue
        if j >= len(part2):
            result.append(part1[i])
            i += 1
            continue
        if custom_compare(part1[i], part2[j]) == (part1[i], part2[j]):
            result.append(part1[i])
            i += 1
        else:
            result.append(part2[j])
            j += 1
    return result

def merge_sort(sn: list):
    while len(sn) > 1:
        result = []
        for i in range(0, len(sn)-1, 2):
            result.append(merge_part(sn[i], sn[i+1]))
        if len(sn) % 2 == 1:
            result.append(sn[-1])
        # print(f"sorting ... : {result}")
        sn = result
    return sn


if __name__ == "__main__":
    n = int(input())
    sn = [[input()] for i in range(n)]
    result = merge_sort(sn)
    print('\n'.join(result[0]))