[Python] Level 2. [3차] 파일명 정렬

프로그래머스

 

문제 설명

files가 주어질 때, head / number / tail로 구성되어 head를 대소문자 상관 없이 오름차순으로 정렬하고, 만약 동일한 경우 number를 오름차순으로 정렬한다.

✅ head는 숫자가 아닌 문자로 구성되어 있다.

✅ number는 숫자이며, 0011과 같이 앞이 0으로 시작할 수도 있다.

 

 

문제 풀이

(1) 사용한 알고리즘

re.split(), sort()

 

(2) 시간복잡도

files의 길이를 n, 파일명 길이를 m이라 할 때 O(n * m)

 

(3) 문제 설명

1. files에서 head와 number 추출하기

🙋‍♀️ 추출하는 방법은 여러 가지가 있겠지만, 저는 re 정규식을 사용했습니다.

 

 

files에서 head는 결국 number의 앞부분이므로, number를 기준으로 split한 문자열에서 head를 추출할 수 있고,

반대로 files에서 숫자가 아닌 문자를 기준으로 split한 문자열에서 numbers를 추출할 수 있다.

 

⭐ re.split(문자열 패턴, 문자열)

설정한 패턴으로 문자열을 split할 수 있는 re의 메소드

• re.split(r'[0-9]+', 문자열): 연속되는 숫자로 문자열을 split
• re.split(r'[^0-9]+', 문자열): 숫자가 아닌 연속되는 문자로 문자열을 split

 

예를 들어, 문자열 "foo010bar020.zip"에서 strings와 numbers는 각각 다음과 같다.

file = "foo010bar020.zip"
strings = re.split(r'[0-9]+', file) # ['foo', 'bar', '.zip'] 
numbers = re.split(r'[^0-9]+', file) # ['', '010', '020', '']

 

✅ 이 때, 숫자가 아닌 문자열로 split하기 때문에 numbers 배열의 맨 앞은 ''로 시작하므로, 이를 제거하는 과정을 추가했다. List Comprehension을 통해 간단하게 제거할 수 있다.

numbers = [num for num in re.split(r'[^0-9]+', file) if num != '']

 

최종적으로 re.split()을 문제에 적용해보면 다음과 같다.

head_and_number = []
for i, file in enumerate(files):
    # head, number 추출
    strings = re.split(r'[0-9]+', file)
    numbers = [num for num in re.split(r'[^0-9]+', file) if num != '']
        
    head_and_number.append((strings[0], int(numbers[0]), i))

✅ head_and_number는 head와 number를 기준으로 file을 재정렬하기 위한 배열로, 재정렬한 이후에 원본 files와 비교하기 위해 인덱스 값도 추가한다. 

 

2. files를 조건에 맞게 정렬하기

• head는 대소문자 구별없이 오름차순 정렬을 하므로, uppercase를 기준으로 오름차순 정렬한다.
• head가 동일할 경우, numbers를 기준으로 오름차순 정렬한다.

head_and_number.sort(key=lambda x: (x[0].upper(), x[1]))

 

정렬이 완료된 head_and_number 배열을 통해 기존의 files를 재정렬한다.

answer = []
for han in head_and_number:
    answer.append(files[han[2]])
return answer

 

(4) 풀이 코드

import re

def solution(files):
    head_and_number = []
    
    for i, file in enumerate(files):
        # head, number 추출
        strings = re.split(r'[0-9]+', file)
        numbers = [num for num in re.split(r'[^0-9]+', file) if num != '']
        
        head_and_number.append((strings[0], int(numbers[0]), i))

    head_and_number.sort(key=lambda x: (x[0].upper(), x[1]))
    
    answer = []
    for han in head_and_number:
        answer.append(files[han[2]])
    return answer