프로그래머스 | 파일명 정렬(JavaScript)

2021년 1월 15일 Velog에 작성한 글을 옮겨온 글입니다.

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

 

정규표현식 캡처 그룹을 활용한 문제 풀이입니다.

풀이

Array.prototype.sort에 인자로 compareFunction을 전달하여 문제에서 정의한 순서대로 파일명을 정렬하는 문제입니다.

정규표현식으로 그룹을 캡처하여 HEAD, NUMBER, TAIL을 나눈 다음, HEAD 부분은 localeCompare 함수로 비교하고, NUMBER 부분은 + 기호를 이용해 숫자로 형 변환하여 비교했습니다.

• (\D+)
  HEAD는 숫자가 아닌 문자로 이루어져 있으며(\D), 최소한 한 글자 이상(+)이다.
• (\d{1, 5})
  NUMBER는 한 글자에서 최대 다섯 글자 사이({1, 5})의 연속된 숫자(\d)로 이루어져 있으며, 앞쪽에 0이 올 수 있다. 0부터 99999 사이의 숫자로, 00000이나 0101 등도 가능하다.
• (?:.*)
  TAIL은 그 나머지 부분(.*)으로, 여기에는 숫자가 다시 나타날 수도 있으며, 아무 글자도 없을 수 있다. TAIL 부분은 필요하지 않아서 캡처하지 않았습니다(?:).

function solution(files) {
    return files.sort((a, b) => {
        const regex = /^(\D+)(\d{1,5})(?:.*)$/;
        const [, aHead, aNumber] = a.match(regex);
        const [, bHead, bNumber] = b.match(regex);
        const compareHead = aHead.toLowerCase().localeCompare(bHead.toLowerCase());
        return compareHead || +aNumber - +bNumber;
    });
}

 

---

정렬 기준 중 "두 파일의 HEAD 부분과, NUMBER의 숫자도 같을 경우, 원래 입력에 주어진 순서를 유지한다." 부분은 sort 알고리즘이 stable한가와 관련된 조건입니다.
V8 엔진에서는 V8 v7.0 / Chrome 70 버전부터 Stable Sorting 알고리즘인 Timsort을 사용하고 있기 때문에 JavaScript 내장 sort 함수를 사용한다면 해당 조건은 신경 쓰지 않아도 됩니다.

cf) Java와 Python은 기본 sort 함수가 Timsort 알고리즘(stable)으로 구현되어 있으나, c++은 Quicksort 알고리즘(unstable)이라 별도로 stable_sort 함수를 이용해야 문제를 해결할 수 있다고 합니다.

---

참고자료
Getting things sorted in V8 https://v8.dev/blog/array-sort
Timsort https://v8.dev/blog/array-sort#timsort
Stable Sort https://v8.dev/features/stable-sort