[정렬]가장 큰 수_Array.prototype.sort()에 대한 고찰

문제

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbersreturn

[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

문제풀이

https://choi95.tistory.com/120?category=881084

순열 구하기

중복을 허용하지 않는 수를 구한다는 점에서 기본적으로 순열 구하기 문제와 같이 깊이 탐색(DFS)를 통해 풀이하였다.

 

코드

function solution(numbers) {
  var answer = "";
  let max = Number.MIN_SAFE_INTEGER;
  let n = numbers.length;
  let ch = Array.from({ length: n }, () => 0);
  let tmp = [];
  
  function DFS(L) {
    if (L === n) {
      max = Math.max(max, Number(tmp.join('')));
      return;
    } else {
      for (let i = 0; i < n; i++) {
        if (ch[i] === 0) {
          ch[i] = 1;
          tmp.push(numbers[i]); //재귀를 한 번씩 호출될 때마다 경우의 수를 임의의 배열에 push
          DFS(L + 1);
          tmp.pop(numbers[i]); //백트래킹을 할 경우에는 가장 마지막으로 참조된 수를 다시 pop
          ch[i] = 0;
        }
      }
    }
  }

  DFS(0);
  answer = String(max);
  return answer;
}

 

오답

코드 실행을 했을 때는 예시 케이스를 모두 통과하였지만 테스트 케이스를 돌렸을 때는 시간 초과로 인해 오답 처리되었다.

문제의 로직은 맞는 것 같지만 재귀 함수를 호출하며 반복문을 순회하는 방식으로 풀었기 때문에 시간 복잡도 효율이 좋지 않은 것 같다.

 

문자열 연결 연산인 +와 염두에 두고 있었다면 굉장히 간단한 문제였다.배열 내 각 요소를 문자 타입으로 치환해준 뒤에 문자 연결 연산을 하여 정렬(sort)만 해주면 되었다.

 

Array.prototype.sort()

해당 문제를 Array.prototype.sort() 메서드에 관해서 중요한 사항을 공부할 수 있어서 포스팅해두고자 한다.

 

지금까지는 sort() 메서드 내 콜백 함수의 두 인자 a, b에 대해서 정말 막연하게 양옆에 붙어 있는 숫자라고만 생각을 했었지만 해당 문제를 풀이하다 보니, 이에 대해서 다시 한 번 생각해보게 되었다.

[5, 3, 4, 2, 1] 
a & b = ( 5, 3 / 3, 4 / 4, 1/ 1, 2 ... )
=> 과연 두 인수가 이런 식으로 단순히 붙어 있는 숫자일까?

 

이에 관련되어 구글링하여 찾아 보니, 그럴 수도 있고 그렇지 않을 수도 있다는 답을 찾을 수 있었다.

자바스크립트 엔진에 설계 된 알고리즘이 계산 절차를 동적으로 결정한다는 것이다.

 

Mozilla는 병합 정렬을 사용하지만 오늘 날 Chrome의 v8 소스 코드에서는 더 작은 배열에 QuickSort 및 InsertionSort를 사용한다.

 

예를 들어 삽입 정렬를 통해 위 배열의 오름차순 정렬 과정을 살펴 보자.

a(기준) - b

5 - 3 = 2 (return 양수 => 순서 바뀜)
3 - 4 = -1 (return 음수 => 순서 그대로)
3 - 2 = 1 (return 양수 => 순서 바뀜)
2 - 1 = 1 (return 양수 => 순서 바뀜)

 

이런 식으로 단순히 자신과 인접해 있는 모든 수를 비교하는 버블 정렬 방식으로 정렬될 수도 있지만 고정된 기준 하에 그 뒤에 값들을 순회하며 비교하는 삽입 정렬 방식으로도 sort() 메서드의 compare 연산 과정이 진행될 수 있다.

 

https://choi95.tistory.com/94

삽입 정렬

 

아직까진 sort() 메서드가 어떻게 동작하는지에 대해서 정확히 파악하지 못하였지만, 이전에 sort() 메서드에 대해 편협된 지식으로 인해 잘 활용하지 못했었기에 해당 문제는 매우 유의미했다.

 

코드

function solution(numbers) {
    const answer = numbers.map((number) => number.toString()).sort((a, b) => (b+a) - (a+b)).join("") //문자열이기에 가능한 + 연결 연산을 통한 value 비교 
    return answer.replace(/^0+/, "0"); // 문자 맨 앞에 0이 1회이상 반복되어질 경우 0으로 치환
}

 

관련 문제_문자열 내 마음대로 정렬하기

function solution(strings, n) {
    var answer = [];
    answer = strings.sort((a, b) => {
      if(a[n].charCodeAt() === b[n].charCodeAt()) {
        let len = Math.max(a.length, b.length);
        for(let i = 0; i < len; i++) {
            if(a[i] !== b[i]) return a[i] - b[i];
        };
      } else return a[n] - b[n]
    });

    return answer;
}