0. 문제
세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다.
저장소 서버에는 프로그램의 과거 버전을 모두 담고 있어, 이름 순으로 정렬된 파일 목록은 보기가 불편했다. 파일을 이름 순으로 정렬하면 나중에 만들어진 ver-10.zip이 ver-9.zip보다 먼저 표시되기 때문이다.
버전 번호 외에도 숫자가 포함된 파일 목록은 여러 면에서 관리하기 불편했다. 예컨대 파일 목록이 ["img12.png", "img10.png", "img2.png", "img1.png"]일 경우, 일반적인 정렬은 ["img1.png", "img10.png", "img12.png", "img2.png"] 순이 되지만, 숫자 순으로 정렬된 ["img1.png", "img2.png", "img10.png", img12.png"] 순이 훨씬 자연스럽다.
무지는 단순한 문자 코드 순이 아닌, 파일명에 포함된 숫자를 반영한 정렬 기능을 저장소 관리 프로그램에 구현하기로 했다.
소스 파일 저장소에 저장된 파일명은 100 글자 이내로, 영문 대소문자, 숫자, 공백(" "), 마침표("."), 빼기 부호("-")만으로 이루어져 있다. 파일명은 영문자로 시작하며, 숫자를 하나 이상 포함하고 있다.
파일명은 크게 HEAD, NUMBER, TAIL의 세 부분으로 구성된다.
- HEAD는 숫자가 아닌 문자로 이루어져 있으며, 최소한 한 글자 이상이다.
- NUMBER는 한 글자에서 최대 다섯 글자 사이의 연속된 숫자로 이루어져 있으며, 앞쪽에 0이 올 수 있다. 0부터 99999 사이의 숫자로, 00000이나 0101 등도 가능하다.
- TAIL은 그 나머지 부분으로, 여기에는 숫자가 다시 나타날 수도 있으며, 아무 글자도 없을 수 있다.
| 파일명 | HEAD | NUMBER | TAIL |
|---|---|---|---|
| foo9.txt | foo | 9 | .txt |
| foo010bar020.zip | foo | 010 | bar020.zip |
| F-15 | F- | 15 | (빈 문자열) |
파일명을 세 부분으로 나눈 후, 다음 기준에 따라 파일명을 정렬한다.
- 파일명은 우선 HEAD 부분을 기준으로 사전 순으로 정렬한다. 이때, 문자열 비교 시 대소문자 구분을 하지 않는다. MUZI와 muzi, MuZi는 정렬 시에 같은 순서로 취급된다.
- 파일명의 HEAD 부분이 대소문자 차이 외에는 같을 경우, NUMBER의 숫자 순으로 정렬한다. 9 < 10 < 0011 < 012 < 13 < 014 순으로 정렬된다. 숫자 앞의 0은 무시되며, 012와 12는 정렬 시에 같은 같은 값으로 처리된다.
- 두 파일의 HEAD 부분과, NUMBER의 숫자도 같을 경우, 원래 입력에 주어진 순서를 유지한다. MUZI01.zip과 muzi1.png가 입력으로 들어오면, 정렬 후에도 입력 시 주어진 두 파일의 순서가 바뀌어서는 안 된다.
무지를 도와 파일명 정렬 프로그램을 구현하라.
1. 어떻게 풀 것인가?
본 문제는 2018 카카오 블라인드 코딩테스트 문제이다.
1.1 Header, Number 분류하기
일단 문제의 조건에 따르면 주어진 파일명을
- Head 부분을 사전순으로 정렬
- Number 부분을 크기 순으로 정렬
- 입력 순서대로 정렬
해야 한다.
따라서 문제의 조건에 따라 우선 파일명을 Header, Number로 나누기로 한다. (Tail은 정렬조건에 포함되지 않으므로 제외한다.)
heads = []
nums = []
orders = []
# head, number 나누기
for file_idx, file in enumerate(files):
head_end = -1 # head가 끝나는 지점
num_end = -1 # number가 끝나는 지점
for ch_idx, ch in enumerate(file): # 파일명의 각 글자
if head_end == -1 :
if ch.isnumeric():
head_end = ch_idx
elif num_end == -1:
if not ch.isnumeric():
num_end = ch_idx
head = file[:head_end]
num = file[head_end:num_end]
order = file_idx
heads.append(head)
nums.append(num)
orders.append(order)1.2 어떻게 정렬하지?
만약 파일명이 모두 문자열이거나 모두 숫자인 경우, 간단히 정렬할 수 있다. 하지만 본 문제에서의 파일명은 숫자와 영어가 합쳐져있으며, 파일명의 길이도 일치하지 않기 때문에 이들 모두를 고려해야 한다.
그러나 파일명을 모두 숫자로 표현하고 이들의 길이가 모두 일치하도록 치환한다면 문제를 쉽게 풀 수 있다.
1.2.1 Head의 경우
우선 조건에 따르면 head는 대소문자를 구분하지 않는다. 따라서 head를 모두 소문자로 치환해주며, 중복을 제거한 후에 정렬하여 그 순서대로 숫자를 매기는 방식으로 head를 정렬하기로 하였다.
예를 들어, 4개의 파일이 각각 aaa, bbb, ccc, ccc의 head를 가지고 있다고 가정하자.
중복을 제거하면 aaa, bbb, ccc만이 남게되고, 이 head를 정렬한 후 숫자로 치환해준다면 각 파일은 1, 2, 3, 3의 head를 가지게 된다.
그러나 중복을 제외한 파일의 개수가 10개가 넘는다고 가정해보자. 어떤 파일은 1의 head를 가지고, 어떤 파일은 10의 head를 가지게 된다. 2의 head를 가진 파일이 10의 head를 가진 파일보다 우선순위가 높지만, 정렬은 문자열을 기준으로 발생하기 때문에 10의 head가 2보다 앞서 정렬될 것이다.
이는 비는 자리수에 0을 채워넣는 것으로 해결할 수 있다. 예를 들어, 1, 2, 3과 같이 숫자를 채워넣는 것이 아니라, 01, 02와 같이 숫자를 채워넣는 것이다.
1.2.2 Number의 경우
문제의 조건에 따르면 number는 0부터 99999까지 최고 5자리의 숫자로 구성된다.
따라서 zfill함수를 통해 number를 모두 다섯 자리로 맞춰준다면 10이 2보다 앞서 정렬되는 것을 방지할 수 있다.
1.2.3 입력 순서의 경우
이 역시 1.2.2의 경우와 같다. 문제의 조건에 따르면 파일은 최대 천 개 까지 주어진다. 마찬가지로 zfill함수를 통해 입력 순서를 모두 네 자리수로 맞춰주면 된다.
1.3 치환 결과
head = file[:head_end].lower()
num = file[head_end:num_end].zfill(5)
order = str(file_idx).zfill(4)대소문자를 가리지 않는 것과, 자리수를 맞춰주는 것을 고려하여 코드를 약간 수정해주었다.
이후 앞서 1.2에 설명한 대로 파일명의 각 부분을 치환한 후 정렬해보도록 하겠다.
예제 입력은 문제에 주어진 것을 활용하도록 한다.
input :
["img12.png", "img10.png", "img02.png", "img1.png", "IMG01.GIF", "img2.JPG"]우선 head는 모두 img기 때문에 전부 1로 치환된다.
숫자부분인 12, 10, 02, 1, 01, 2는 다섯자리로 변환되어 00012, 00010, 00002, 00001, 00001, 00002로 변환된다.
또한, 입력 순서에 따라 네 자리의 코드가 부여되어 input은 다음과 같은 형태로 변화된다.
['1000120000', '1000100001', '1000020002', '1000010003', '1000010004', '1000020005']이제 해당 숫자를 정렬한 후에, 정렬된 값을 원래 글자로 바꿔주면 된다.
정렬된 값을 원래 글자로 바꿔줄 때에는 맨 마지막 네 자리의 숫자를 활용할 수 있다.
2. 코드
def solution(files):
answer = []
heads = []
nums = []
orders = []
# head, number 나누기
for file_idx, file in enumerate(files):
head_end = -1 # head가 끝나는 지점
num_end = -1 # number가 끝나는 지점
for ch_idx, ch in enumerate(file): # 파일명의 각 글자
if head_end == -1 :
if ch.isnumeric():
head_end = ch_idx
elif num_end == -1:
if not ch.isnumeric():
num_end = ch_idx
else:
break
head = file[:head_end].lower()
if num_end != -1:
num = file[head_end:num_end].zfill(5)
else:
num = file[head_end:].zfill(5)
order = str(file_idx).zfill(4)
heads.append(head)
nums.append(num)
orders.append(order)
# head 치환
heads_no_dup = list(set(heads))
heads_no_dup.sort()
head_dict = {value:idx+1 for idx, value in enumerate(heads_no_dup)}
for head_idx in range(len(heads)):
head = heads[head_idx]
heads[head_idx] = str(head_dict[head]).zfill(4)
# 합쳐주기
new_files = ["".join(x) for x in zip(heads, nums, orders)]
new_files.sort()
for new_file in new_files:
order = int(new_file[-4:])
answer.append(files[order])
return answer4. 비고
구글링해서 찾아보니 lambda 함수를 이용하면 sort에 우선순위를 정해줄 수 있다고 한다. 미리 알았다면 더 빨리 풀 수 있었을 것 같다.
