[Python/파이썬] 백준 20210번 파일 탐색기

20210번: 파일 탐색기

 

문제

Windows의 파일 탐색기를 보면 파일이 정렬된 방식이 보통의 정렬 방식과는 다른 것을 알 수 있다.

보통 문자열을 정렬할 때는 맨 앞부터 한 글자씩 비교하다가 어느 한쪽이 끝나거나 일치하지 않는 글자가 있으면 그 위치의 문자를 비교한 결과가 문자열 전체를 비교한 결과가 된다. 한편 파일 탐색기는 여러 자리의 수를 한 글자로 취급해서 비교하는데, 이 때문에 "str12ing"과 "str123ing" 중 후자가 아니라 전자가 앞에 온다. 이러한 정렬 방식을 종종 "natural sort"라고 하기도 한다.

여러 개의 문자열이 주어지면 natural sort 방식으로 정렬한 결과를 출력하는 프로그램을 작성해 보자. 이 문제에서 구현할 알고리즘은 다음을 만족해야 한다.

1. 문자열은 알파벳 대소문자와 숫자로만 이루어져 있다.
2. 숫자열이 알파벳보다 앞에 오고, 알파벳끼리는 AaBbCc...XxYyZz의 순서를 따른다.
3. 문자열을 비교하는 중 숫자가 있을 경우 그 다음에 오는 숫자를 최대한 많이 묶어 한 단위로 비교한다. 예를 들어 "a12bc345"는 "a", "12", "b", "c", "345"의 다섯 단위로 이루어져 있다.
4. 숫자열끼리는 십진법으로 읽어서 더 작은 것이 앞에 온다. 이때 예제 2에서와 같이 값이 263을 초과할 수 있다.
5. 같은 값을 가지는 숫자열일 경우 앞에 따라붙는 0의 개수가 적은 것이 앞에 온다.

입력

첫 줄에 문자열의 개수 N(2 ≤ N ≤ 10,000)이 주어진다. 그 다음 N줄에 정렬할 문자열이 한 줄에 하나씩 주어진다.

모든 문자열의 길이는 100 이하이며, 알파벳 대소문자와 숫자로만 이루어져 있다.

출력

N줄에 걸쳐 문제에서 설명한 대로 문자열을 정렬한 결과를 출력한다.

코드

import sys
input = sys.stdin.readline
from functools import cmp_to_key
    
# 문자열 파싱
def parse(str):
    res = []
    i = 0
    while i < len(str):
        if str[i].isalpha():    # 알파벳인 경우
           res.append(str[i]) 
           i += 1
        else:   # 숫자인 경우
            tmp = ''
            while i < len(str) and str[i].isdigit():
                tmp += str[i]
                i += 1
            res.append(tmp)
    return res

def natural_sort(str1, str2):
    lst1 = parse(str1)
    lst2 = parse(str2)
    idx = 0
    while idx < min(len(lst1), len(lst2)):
        if lst1[idx] == lst2[idx]:
            idx += 1
            continue
        # 하나는 숫자, 하나는 문자인 경우
        if lst1[idx].isdigit() and lst2[idx].isalpha():
            return -1
        if lst1[idx].isalpha() and lst2[idx].isdigit():
            return 1
        # 둘 다 문자인 경우
        if lst1[idx].isalpha() and lst2[idx].isalpha():
            if lst1[idx].lower() == lst2[idx].lower():  # 같은 문자이지만 대소문자로 다른 경우
                return 1 if lst1[idx] > lst2[idx] else -1   # 대문자 아스키 코드 < 소문자 아스키 코드
            else:                                       # 다른 문자인 경우
                return 1 if lst1[idx].lower() > lst2[idx].lower() else -1
        # 숫자인 경우
        if lst1[idx].isdigit() and lst2[idx].isdigit():
            if int(lst1[idx]) == int(lst2[idx]):
                return 1 if len(lst1[idx]) > len(lst2[idx]) else -1
            else:
                return 1 if int(lst1[idx]) > int(lst2[idx]) else -1
    return 1 if len(lst1) > len(lst2) else -1
        
lst = []
for _ in range(int(input())):
    lst.append(input().strip())   

for el in sorted(lst, key=cmp_to_key(natural_sort)):
    print(el)

• parse()
  : 파라미터로 받은 문자열을 문자는 한 문자씩, 숫자는 여러 자리이더라도 하나로 묶어서 리스트로 만들어서 리턴.
  예를 들어, abs123def는 ['a', 'b', 'c', '123', 'd', 'e', 'f']로 리턴
• natural_sort()
  : 파라미터로 문자열 2개(str1, str2)를 받아서 문제에 주어진 정렬 조건에서 str1이 더 앞에 오면 -1, str2가 더 앞에 오면 1 리턴.
  
  
• functools 모듈의 cmp_to_key

functools — Higher-order functions and operations on callable objects