문제 요약
파일명은 HEAD, NUMBER, TAIL 세 부분으로 나뉜다.
HEAD: 숫자가 아닌 문자로 이루어진 부분
NUMBER: 연속된 숫자로 이루어진 부분
TAIL: NUMBER 뒤에 남은 나머지 부분파일명을 다음 기준으로 정렬해야 한다.
1. HEAD를 대소문자 구분 없이 사전순 정렬
2. HEAD가 같으면 NUMBER를 숫자값 기준으로 정렬
3. HEAD와 NUMBER가 모두 같으면 원래 입력 순서 유지핵심 아이디어
파일명 전체를 문자열 기준으로 정렬하면 숫자의 자릿수 때문에 자연스러운 순서가 만들어지지 않는다.
문자열 정렬: img1, img10, img12, img2
원하는 정렬: img1, img2, img10, img12따라서 파일명에서 HEAD와 NUMBER를 분리한 뒤 정렬 키로 사용한다.
(head.lower(), int(number))TAIL은 정렬 기준에 포함되지 않는다.
파이썬의 sorted 함수는 안정 정렬이다.
정렬 키가 완전히 같은 원소들은 입력에서의 상대적인 순서가 유지된다.
따라서 입력 인덱스를 별도로 정렬 키에 넣지 않아도 세 번째 조건을 만족할 수 있다.
HEAD, NUMBER, TAIL 분리
파일명은 영문자로 시작하고 숫자를 하나 이상 포함한다.
따라서 앞에서부터 처음 숫자가 나오는 위치를 찾으면 HEAD의 끝을 알 수 있다.
index = 0
while not filename[index].isdigit():
index += 1처음 숫자가 나온 위치 이전까지가 HEAD다.
head = filename[:index]숫자가 시작한 위치부터 연속된 숫자를 읽으면 NUMBER를 얻을 수 있다.
number_start = index
while (
index < len(filename)
and filename[index].isdigit()
and index - number_start < 5
):
index += 1
number = filename[number_start:index]NUMBER는 최대 다섯 자리까지 읽는다.
NUMBER 뒤의 나머지는 TAIL이지만 정렬 기준에 사용하지 않으므로 따로 저장할 필요가 없다.
HEAD 정렬
HEAD는 대소문자를 구분하지 않는다.
head.lower()예를 들어 다음 HEAD들은 정렬할 때 같은 값으로 취급된다.
MUZI
muzi
MuZi원래 파일명 자체를 바꾸는 것이 아니라 정렬 키를 만들 때만 lower를 사용한다.
NUMBER 정렬
NUMBER는 문자열이 아니라 숫자값으로 비교한다.
int(number)앞쪽의 0은 숫자 비교에서 무시된다.
"0011" -> 11
"012" -> 12
"12" -> 12따라서 다음 순서가 자연스럽게 만들어진다.
9 < 10 < 0011 < 012 < 13 < 014012와 12처럼 숫자값이 같은 경우에는 안정 정렬에 의해 원래 입력 순서가 유지된다.
안정 정렬
정렬 키가 같은 두 파일을 생각해보자.
MUZI01.zip
muzi1.png두 파일의 키는 모두 다음과 같다.
("muzi", 1)파이썬의 sorted는 같은 키를 가진 원소의 상대 순서를 바꾸지 않는다.
따라서 입력에서 MUZI01.zip이 먼저였다면 정렬 결과에서도 먼저 유지된다.
풀이 과정
- 파일명에서 처음 숫자가 나오는 위치를 찾는다.
- 처음 숫자 전까지를 HEAD로 분리한다.
- 최대 다섯 자리의 연속된 숫자를 NUMBER로 분리한다.
- HEAD를 소문자로 변환하고 NUMBER를 정수로 변환한다.
- 두 값을 튜플 정렬 키로 사용한다.
- 안정 정렬로 같은 키의 원래 순서를 유지한다.
Python 코드
def solution(files):
def get_sort_key(filename):
index = 0
# HEAD의 끝, 즉 처음 숫자가 나오는 위치를 찾는다.
while not filename[index].isdigit():
index += 1
head = filename[:index]
number_start = index
# NUMBER는 최대 다섯 자리의 연속된 숫자다.
while (
index < len(filename)
and filename[index].isdigit()
and index - number_start < 5
):
index += 1
number = filename[number_start:index]
# TAIL은 정렬 기준이 아니므로 사용하지 않는다.
return head.lower(), int(number)
return sorted(files, key=get_sort_key)코드 설명
처음 숫자 찾기
while not filename[index].isdigit():
index += 1파일명은 영문자로 시작하고 숫자를 하나 이상 포함하므로, 범위를 벗어나지 않고 처음 숫자 위치를 찾을 수 있다.
HEAD에는 공백, 마침표, 빼기 부호처럼 숫자가 아닌 문자도 포함될 수 있다.
isdigit을 사용하면 영문자가 아니더라도 숫자가 아닌 모든 HEAD 문자를 자연스럽게 처리할 수 있다.
NUMBER 범위
while (
index < len(filename)
and filename[index].isdigit()
and index - number_start < 5
):
index += 1NUMBER는 숫자로만 이루어지고 길이가 최대 다섯 자리다.
숫자가 아닌 문자를 만나거나 다섯 자리를 읽으면 NUMBER 분리를 멈춘다.
정렬 키
return head.lower(), int(number)튜플은 앞쪽 원소부터 순서대로 비교한다.
따라서 HEAD를 먼저 비교하고, HEAD가 같을 때 NUMBER를 비교하는 조건을 그대로 표현할 수 있다.
TAIL을 사용하지 않는 이유
foo010bar020.zip
HEAD: foo
NUMBER: 010
TAIL: bar020.zip문제의 정렬 기준은 HEAD와 NUMBER까지만 사용한다.
TAIL은 HEAD와 NUMBER가 모두 같을 때도 비교하지 않고, 원래 입력 순서를 유지해야 하므로 정렬 키에 넣으면 안 된다.
예시
다음 파일 목록을 살펴보자.
files = [
"img12.png",
"img10.png",
"img2.png",
"img1.png",
]각 파일의 정렬 키는 다음과 같다.
| 파일명 | HEAD 키 | NUMBER 키 |
|---|---|---|
| img12.png | img | 12 |
| img10.png | img | 10 |
| img2.png | img | 2 |
| img1.png | img | 1 |
NUMBER를 정수로 비교하므로 결과는 다음과 같다.
[
"img1.png",
"img2.png",
"img10.png",
"img12.png",
]시간 복잡도
파일 개수를 N, 파일명 하나의 최대 길이를 L이라고 하자.
정렬 키를 만들기 위해 각 파일명을 한 번 읽는다.
O(N x L)이후 N개 파일을 정렬한다.
O(N log N)파일명 길이는 최대 100이므로 전체 시간 복잡도는 정렬이 지배한다.
O(N log N)공간 복잡도
파이썬의 정렬 과정에서 정렬 키와 결과 배열을 위한 추가 공간이 사용된다.
O(N)정리
이 문제는 파일명을 정렬 기준에 맞게 분리해 사용자 정의 키로 정렬하는 구현 문제다.
처음 숫자 위치를 찾아 HEAD 분리
최대 다섯 자리 숫자를 NUMBER로 분리
HEAD는 lower로 비교
NUMBER는 int로 비교
TAIL은 정렬 키에서 제외
안정 정렬로 같은 키의 입력 순서 유지문자열 전체를 비교하지 않고, 문제에서 정의한 HEAD와 NUMBER만 정확히 추출해 정렬 키로 만드는 것이 핵심이다.
