KAKAO BLIND RECRUITMENT 3차 - 파일명 정렬

Algorithm
KAKAO BLIND RECRUITMENT 3차, algorithm, 프로그래머스

프로그래머스 문제링크

카카오 블라인드 테스트 엄청 어렵다. 그나마 이 문제가 그 중에서 쉬운 문제였을 것 같은데,
배열의 sort메소드로 풀다가 sort 메소드가 안전 정렬(stable sorting)이 아니라는 것이 기억나서 해당 메소드를 안전 정렬로 만들어 주는 방법을 찾았다.
해당 방법을 참고해서 겨우겨우 통과하긴 했는데, sort를 어떻게 안정적으로 만드냐를 알게 된 것에 의의를 둬야겠다.

자바스크립트에서 배열의 sort메소드에 인자로 전달되는 비교 함수(compareFunction(a, b))이 반환하는 값이

  • 0보다 작으면 a가 먼저 온다.(a가 b보다 낮은 색인 정렬)
  • 0보다 크면 b가 먼저 온다.
  • 0이면 a와 b를 변경하지 않고 모든 다른 요소에 대해 정렬하는데, 이때 ECMAscript 표준은 이러한 동작을 보장하지 않는다고 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function solution(files) {
    let answerWrap = files.map((file, index) => ({file, index}));
    const compare = (a, b) => {
      const reg = /(\D*)(\d*)/i;
      const A = a.match(reg);
      const B = b.match(reg);
      const compareHead = A[1].toLowerCase().localeCompare(B[1].toLowerCase());
      const compareNumber = (a, b) => {
         return parseInt(a) > parseInt(b) ? 
            1 : parseInt(a) < parseInt(b) ? 
             -1 
            : 0
      }
      return compareHead === 0 ? compareNumber(A[2], B[2]) : compareHead
    }
    answerWrap.sort((a, b) => {
      const result = compare(a.file, b.file);
      return result === 0 ? a.index - b.index : result;
    })
    return answerWrap.map(answer => answer.file);
}

해당 방법은 map 메소드를 이용해 요소와 인덱스 정보를 가진 객체를 요소로 가지는 배열을 만들어서
비교함수에서는 요소간 비교하고, 반환되는 값이 0일때는 인덱스 정보를 이용해 원래 위치를 비교해 정확한 순서를 얻는다.

Share Comments