[프로그래머스] 파일명 정렬

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

프로그래머스

문제 설명

 

소스 파일 저장소에 저장된 파일명은 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가 입력으로 들어오면, 정렬 후에도 입력 시 주어진 두 파일의 순서가 바뀌어서는 안 된다.
무지를 도와 파일명 정렬 프로그램을 구현하라.

---

제한 사항

입력으로 배열 files가 주어진다.

files는 1000 개 이하의 파일명을 포함하는 문자열 배열이다.
각 파일명은 100 글자 이하 길이로, 영문 대소문자, 숫자, 공백(" "), 마침표("."), 빼기 부호("-")만으로 이루어져 있다. 파일명은 영문자로 시작하며, 숫자를 하나 이상 포함하고 있다.
중복된 파일명은 없으나, 대소문자나 숫자 앞부분의 0 차이가 있는 경우는 함께 주어질 수 있다. (muzi1.txt, MUZI1.txt, muzi001.txt, muzi1.TXT는 함께 입력으로 주어질 수 있다.)
출력 형식
위 기준에 따라 정렬된 배열을 출력한다.

---

풀이

 

로직

1. 형태가 일정할 문자열 → 정규 표현식으로 풀기
2. 대소문자 구분이 없다했으니 lower 사용해 소문자로 통일
3. head, int, index 튜플 형태로 저장해서 sort 하면 head → int → index 순으로 정렬됨
4. 정렬된 list의 index만 읽어서 재구성

 

초기 코드 : 정규 표현식

# 초기 코드 : 정규 표현식
import re
def solution(files):
    answer = []
    for idx, file in enumerate(files):
        file_lower = file.lower()
        match = re.search(r'^(.*?)(\d+)', file_lower)
        head, numbers = match.groups()
        f = (head, int(numbers), idx)
        answer.append(f)
    answer.sort()
    answer = [files[i] for _, _, i in answer]
    return answer
# 3.55ms, 10.6MB

 

로직대로 코드를 구성했는데 개선할 점이 보인다.

1.  lower의 위치 : 대소문자의 영향을 받는 것은 head 부분이니깐 head.lower() 해주면 조금 더 효율적이다.
2.  정규식의 위치 : 정규식이 일정하니 그냥 컴파일해놓고 쓰는편이 더 효율적이다.

 

1차 수정 : 로직 변경

# 1차 수정 : 로직 변경
import re
def solution(files):
    answer = []
    pattern = re.compile(r'^(.*?)(\d+)')
    for idx, file in enumerate(files):
        match = pattern.search(file)
        head, numbers = match.groups()
        f = (head.lower(), int(numbers), idx)
        answer.append(f)
    answer = [files[idx] for _, _, idx in sorted(answer)]
    return answer
# 2.80ms, 10.6MB

 

20% 정도 효율이 좋아졌다. 더 개선할 점이 보이지 않아서 다른 방법으로도 풀어보았다.

 

2차 수정 : 정규 표현식 사용하지 않고 풀기

# 2차 수정 : 정규 표현식 사용하지 않고 풀기
def solution(files):
    answer = []
    for idx, file in enumerate(files):
        head, number = "", ""
        number_started = False
        for char in file:
            if char.isdigit():
                number += char
                number_started = True
            elif not number_started:
                head += char
            else:
                break
        answer.append((head.lower(), int(number), idx))
    answer = [files[i] for _, _, i in sorted(answer)]
    return answer
# 3.45ms, 10.5MB

 

head 부분은 숫자를 제외한 문자,

number 부분은 연속된 숫자로만 이루어진 문자라서 

위와같은 조건을 짜놓으면  head와 number를 나눌 수 있다.

나머지 로직은 1차 수정 코드와 동일. 다만 2중 for문을 사용하기 때문에 시간효율은 좋지 않다.