[3차] 파일명 정렬 (with Python3)

https://programmers.co.kr/learn/courses/30/lessons/17686

코딩테스트 연습 - [3차] 파일명 정렬

이해하기

files에 있는 단일 문자를 f이라고 하자.

f을 HEAD부분 NUMBER부분 TAIL부분으로 나누어서 문제에 조건대로 정렬하는 문제이다.

파이썬에는 sorted or list.sort()에 파라미터로 key가 있으므로 HEAD, NUMBER, TAIL부분으로 잘 나누어 주면 되는 문제이다.

여기서 HEAD, NUMBER 공간은 반드시 존재하지만 TAIL 공간은 존재 안 할 수도 있다.

 

구현하기

문자를 부분적으로 찾는 문제이니 정규표현식을 사용하면 편하다.

하지만 나는 정규표현식에 대해서 잘 알지 못하므로 정규표현식으로 한 줄로 풀지는 못했지만 실전에서는 한 줄 풀이보다는 정규표현식의 도움만 받아서 구현하는게 더 낫다고 생각한다. (나는 문제를 보자마자 한 줄 풀이가 바로 떠올리지 못한다.)

 

HEAD는 f에서 처음으로 숫자가 나오는 인덱스 전까지이다.

그러므로 정규표현식 '\d'를 이용해서 언제 숫자가 나오는지 얻어낸다.

NUMBER는 f에서 숫자가 나오는 부분부터 인덱싱한 문자열에서 처음으로 숫자를 제외한 문자가 나오는 인덱스 전까지다.

그러므로 f[(처음으로 숫자가 나오는 인덱스):] 인덱싱한 문자열에서 정규표현식 '\D'를 이용해서 언제 숫자를 제외한 문자가 나오는지 얻어낸다.

 

여기서 TAIL은 빈 문자열이라면 정규표현식을 사용하더라도  숫자를 제외한 문자가 안 나올 수 있다.

이 상황을 고려하지 않는다면 인덱스 처리시 런타임에러(인덱스 범위 초과)가 발생할 수 있다.

그렇기 때문에 여기서 조건문을 통해서 TAIL이 있는지 없는지 체크하여 윗 상황을 처리한다.

 

여기 까지 했다면 우리는 문제에서 원하는 조건을 맞춰주어야 한다.

HEAD는 대소문자를 구분하지 않는 정렬이 필요하므로 processed_head에 HEAD문자를 소문자형태로 변환해 저장한다.

NUMBER는 앞에 0을 제외하고 숫자순으로 정렬이 필요하므로 int함수를 이용해서 앞에 0을 떼네고 숫자형태로 processed_number에 저장한다.

 

그 저장된 두개의 데이터를 바탕으로 정렬해야 하는데 두 개의 순서가 같으면 원래 순서를 유지해야 한다.

그렇기에 나는 file이라는 리스트에 [HEAD, NUMBER, TAIL, processed_head, processed_number]를 저장해둘 것이다.

여기서 공간복잡도를 생각해서 새로운 리스트에 넣어야하는데 files에 최대크기는 1000이고 그리고 각각 파일명은 100글자 이하이므로 file리스트는 최대크기가 1000이고 가지는 요소는 200(100 + 100)글자 이하를 가지는 리스트로 이루어져 있으므로

그렇게 크지않아서 저장해도 상관없다. (만약 너무컸다면 리스트에 files를 가르키는 index로 원래 위치를 저장했을 것이다.)

 

이제 정렬만 하고 출력만 하면된다.

file.sort(key=lambda x : (x[-2], x[-1]))

x[-2] => processed_head

x[-1] => processed_number

먼저 가공된 헤드인 processed_head로 정렬하고 같다면 가공된 넘버인 processed_number로 정렬해라.

그리고 answer 리스트에 HEAD, NUMBER, TAIL을 더한 문자열을 넣어주면 된다.

 

위 내용을 바탕으로 구현해보자.

import re

def solution(files):
    answer = []
    file = []
    number_p = re.compile('\d') # 숫자 문자형태 패턴
    char_p = re.compile('\D') # 숫자를 제외한 문자형태 패턴
    for f in files:
        number_start = number_p.search(f).start() # 처음으로 오는 숫자문자 인덱스 (반드시 존재)
        head = f[:number_start]
        
        tail_space = char_p.search(f[number_start:]) # 숫자문자 이후에 오는 문자열에서 처음으로 오는 숫자를 제외한 문자 인덱스 (존재 안 할수도 있다.)
        if tail_space: # 존재한다면 start함수 사용가능
            tail_start = tail_space.start()
            number = f[number_start:][:tail_start]
            tail = f[number_start:][tail_start:]
        else: # 존재하지 않으면 TAIL은 빈 문자열
            number = f[number_start:]
            tail = ""
            
        processed_head = head.lower() # HEAD문자 모두 소문자로 가공해서 정렬에 영향이 안가도록한다.
        processed_number = int(number) # NUMBER문자에 오로지 숫자형태로 가공해서 정렬이 숫자순으로 정렬하도록 한다.
        file.append([head, number, tail, processed_head, processed_number])
    file.sort(key=lambda x : (x[-2], x[-1])) # 가공된 헤드로 먼저 정렬, 그리고 가공된 넘버로 정렬, 두 부분이 같다면 원래 순서 유지
    for f in file:
        answer.append(f[0] + f[1] + f[2]) # 가공된 헤드와 가공된 넘버는 원래 데이터를 변경시켰으므로 답으로 포함시키면 안된다.
    return answer