[solved.ac 골드2] 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줄에 걸쳐 문제에서 설명한 대로 문자열을 정렬한 결과를 출력한다.

예제

---

나의 풀이

주어진 문자 분리하기

문제에 따르면 "a12bc345" 문자가 주어지면  "a", "12", "b", "c", "345"와 같이 문자는 각자, 연속된 숫자는 하나의 숫자처럼 다뤄야 한다.

def to_list(word):
    li = list(word)
    i = 0
    while i < len(li):
        if li[i].isdigit():
            end = i
            while end < len(li) and li[end].isdigit():
                end += 1
            li[i:end] = [''.join(li[i:end])]
            i = end - 1
        i += 1
    return li

주어진 word를 list() 함수로 모두 분리한 후에 연속된 숫자는 다시 하나의 문자로 묶어주는 to_list() 함수를 작성했다.

 

Python에서 정렬하는 새로운 방법

Python3에서 sort()나 sorted() 함수(이하 정렬 함수)를 사용해서 정렬을 하는 것이 일반적이다. 정렬 함수에서는 key라는 옵션을 사용할 수 있는데 이 때 key의 값으로 올 수 있는 것은 하나의 매개변수를 받는 함수이다.예를 들어 길이를 기준으로 정렬하고 싶을 때 [리스트].sort(key=len) 과 같이 할 수 있다.len() 함수는 길이를 반환하기 때문에 그 길이를 기준으로 정렬을 하므로 하나의 매개변수 만으로도 정렬을 할 수 있는 것이다.그러나 이 문제에서는 하나의 매개변수 만을 가지고 정렬하기는 쉽지 않다.Java와 같은 다른 함수에서 정렬을 할 때는 Comparator 객체의 compare에서 2개의 매개변수를 받아 우선 순위를 정하도록 한다.아마 많은 사람들이 모를 수도 있지만 Python에서도 이러한 것이 가능하다. 다만 Python2에서는 [리스트].sort(cmp=함수)로 할 수 있었지만 Python3에서는 cmp 옵션이 없어졌다. 대신 functools.cmp_to_key 를 사용해서 동일한 동작을 할 수 있다.

 from functools import cmp_to_key
 [리스트].sort(cmp_to_key=(함수))

 

정렬 기준 함수 작성

이제 cmp_to_key에 넘겨 줄 함수를 작성해보자. 주의할 점은 return 값을 True / False 가 아닌 음수 / 0 / 양수로 반환해야 한다는 점이다.

cmp_to_key 는 위와 같이 되어있다. 함수의 반환 값이 음수면 왼쪽이 작고, 양수면 오른쪽이 작고, 0이면 두 수가 같은 것이다.즉, 이러한 상황에 맞게 -1, 0, 1을 반환하면 된다.

 

def diff(w1, w2):
    w1 = to_list(w1)
    w2 = to_list(w2)
    i = 0
    while i < min(len(w1), len(w2)):
        if w1[i] == w2[i]:
            i += 1
            continue
        # 숫자와 문자 비교
        if w1[i].isdigit() and w2[i].isalpha():
            return -1
        elif w1[i].isalpha() and w2[i].isdigit():
            return 1
        # 문자와 문자 비교
        elif w1[i].isalpha() and w2[i].isalpha():
            if w1[i].lower() == w2[i].lower():
                return -1 if w1[i] < w2[i] else 1
            return -1 if w1[i].lower() < w2[i].lower() else 1
        # 숫자와 숫자 비교
        elif w1[i].isdigit() and w2[i].isdigit():
            if int(w1[i]) == int(w2[i]):
                z1 = len(w1[i])-len(w1[i].lstrip('0'))
                z2 = len(w2[i])-len(w2[i].lstrip('0'))
                return -1 if z1 < z2 else 1
            else:
                return -1 if int(w1[i]) < int(w2[i]) else 1
        i += 1
    return -1 if len(w1) < len(w2) else 1

앞서 만들었던 to_list() 함수를 사용해 두 문자를 리스트 화 하고, 둘을 하나씩 비교한다.

문제의 요구사항에 맞게 작성한 것이므로 단순한 구현 문제이다. 크게 어려운 알고리즘이나 문법은 없으니 천천히 읽어보면 어렵지 않게 이해할 수 있다.

 

입력 받아서 정렬해보기

# 짧은 코드
print(*sorted([input() for _ in range(int(input()))], key=cmp_to_key(diff)), sep='\n')

이제 개수와 문자를 입력 받아 위에서 작성한 함수들을 사용해 실제로 정렬해보는 것이다.

한 줄로 짧게 구현하긴 했는데 풀어서 작성하면 다음과 같다. (파이썬 리스트 컴프리헨션 최고...)

위 코드처럼 print함수에 * 을 사용한 문법이 궁금하다면 다음 게시글을 참고해보자!

2022.05.05 - [python] 숫자(int) 리스트 한 줄에 출력하는 3가지 방법 (반복, join, *)

[python] 숫자(int) 리스트 한 줄에 출력하는 3가지 방법 (반복, join, *)

 

# 긴 코드
n = int(input())
files = []

for _ in range(n):
    file = input()
    files.append(file)
files.sort(key=cmp_to_key(diff))

for file in files:
    print(file)

* 8 줄을 한 줄로 작성할 수 있었다. (짧은 코드에서는 바로 print()에 반환해주기 위해 sorted를 사용했고, 긴 코드에서는 sort로 정렬했다)

sort의 옵션으로 key=cmp_to_key() 를 사용했다.

 

전체 코드

from functools import cmp_to_key


def to_list(word):
    li = list(word)
    i = 0
    while i < len(li):
        if li[i].isdigit():
            end = i
            while end < len(li) and li[end].isdigit():
                end += 1
            li[i:end] = [''.join(li[i:end])]
            i = end - 1
        i += 1
    return li


def diff(w1, w2):
    w1 = to_list(w1)
    w2 = to_list(w2)
    i = 0
    while i < min(len(w1), len(w2)):
        if w1[i] == w2[i]:
            i += 1
            continue
        # 숫자와 문자 비교
        if w1[i].isdigit() and w2[i].isalpha():
            return -1
        elif w1[i].isalpha() and w2[i].isdigit():
            return 1
        # 문자와 문자 비교
        elif w1[i].isalpha() and w2[i].isalpha():
            if w1[i].lower() == w2[i].lower():
                return -1 if w1[i] < w2[i] else 1
            return -1 if w1[i].lower() < w2[i].lower() else 1
        # 숫자와 숫자 비교
        elif w1[i].isdigit() and w2[i].isdigit():
            if int(w1[i]) == int(w2[i]):
                z1 = len(w1[i])-len(w1[i].lstrip('0'))
                z2 = len(w2[i])-len(w2[i].lstrip('0'))
                return -1 if z1 < z2 else 1
            else:
                return -1 if int(w1[i]) < int(w2[i]) else 1
        i += 1
    return -1 if len(w1) < len(w2) else 1

# answer
print(*sorted([input() for _ in range(int(input()))], key=cmp_to_key(diff)), sep='\n')

 

채점 결과

Python3로는 시간 초과가 발생해서 PyPy3로 동일한 코드를 제출해서 통과할 수 있었다.