← 알고리즘 목록
정렬 시간 O(n log n) · 공간 O(n)

비교 함수 정렬

크기 순서로는 답이 나오지 않을 때, 두 원소를 받아 누가 앞에 설지 알려 주는 비교 함수를 직접 만들어 정렬합니다.

대표 문제

언제 쓰나

원소를 어떤 순서로 늘어놓아야 하는데, 그 순서가 값의 크기만으로 정해지지 않을 때 씁니다.

  • 두 원소를 나란히 놓아 봐야 누가 앞인지 알 수 있습니다. 이 글의 대표 문제처럼 수를 이어 붙여 가장 큰 수를 만드는 경우가 여기에 해당합니다.
  • 기준이 여러 개입니다. “점수가 높은 순, 점수가 같으면 이름 순”처럼 첫 기준이 같을 때 다음 기준으로 넘어가야 합니다.

어떻게 동작하나

크기 순서로는 답이 나오지 않는다

LeetCode 179는 0 이상의 정수 배열을 받아, 수들을 한 줄로 이어 붙였을 때 가장 큰 수를 문자열로 돌려주는 문제입니다. nums = [3, 30, 34, 5, 9]이면 답은 "9534330"입니다.

먼저 떠오르는 방법 두 가지로 해 보겠습니다.

  1. 수의 크기가 큰 순서: 34, 30, 9, 5, 3을 이어 붙이면 "3430953"입니다. 앞자리가 3이라 답보다 한참 작습니다.
  2. 문자열 사전 순의 역순: 9, 5, 34, 30, 3을 이어 붙이면 "9534303"입니다. 앞자리는 맞았지만 끝의 303이 답의 330보다 작습니다.

두 번째 방법이 틀린 곳은 3과 30의 순서 하나입니다. 사전 순에서는 "3"이 "30"의 앞부분이라 "30"이 더 뒤에 오는 문자열로 취급되고, 역순으로 뒤집으면 30이 3보다 앞에 섭니다. 하지만 이어 붙인 결과는 3을 앞에 둔 330이 30을 앞에 둔 303보다 큽니다.

두 수를 직접 이어 붙여 보고 정한다

그래서 두 수 a, b 중 누가 앞에 설지는 크기가 아니라 이어 붙인 결과로 정합니다. a를 앞에 둔 a + b와 b를 앞에 둔 b + a를 만들어 보고, 더 큰 쪽의 앞 조각이 앞에 섭니다. 아래 그림은 a = 3, b = 30일 때입니다.

3 a 30 b a + b 330 더 큼 b + a 303 더 큼

a + b가 "330", b + a가 "303"이라 a인 3이 앞에 섭니다. 두 문자열은 같은 조각을 순서만 바꿔 붙였으니 길이가 같고, 길이가 같은 숫자 문자열은 사전 순으로 비교한 결과가 수의 크기 비교와 같습니다. 그래서 큰 수로 바꾸지 않고 문자열 그대로 비교해도 됩니다.

두 수씩만 보고 정한 순서가 전체에서도 가장 크다는 것은 이렇게 확인할 수 있습니다. 완성된 문자열에서 이웃한 두 수가 이 규칙을 어기고 있다면, 그 둘의 자리를 바꾸는 것만으로 앞부분은 그대로 두고 그 자리의 숫자를 키울 수 있습니다. 가장 큰 배치에는 이렇게 바꿀 곳이 남아 있지 않으므로, 모든 이웃이 규칙을 지키는 순서, 즉 이 규칙으로 정렬한 순서가 답이 됩니다.

이처럼 두 원소를 받아 누가 앞에 설지 알려 주는 함수를 비교 함수(comparator)라고 합니다. JavaScript의 sort에 비교 함수를 넘기면, 반환값의 부호로 순서를 정합니다.

  • 음수: a를 b보다 앞에 둡니다.
  • 양수: b를 a보다 앞에 둡니다.
  • 0: 두 원소의 순서를 바꾸지 않습니다.

직접 따라가 보기

아래에서는 sort 대신 삽입 정렬로 비교를 하나씩 실행합니다. 이미 줄을 선 앞쪽 수들 사이에, 뒤에서 한 장씩 꺼낸 수(b)를 비교해 가며 끼워 넣는 방식입니다. 카드 아래 두 줄은 앞에 있던 수 a와 꺼낸 수 b를 두 가지로 이어 붙인 결과이고, 더 큰 줄에 “더 큼”이 붙습니다.

2번째 단계에서 위 그림과 같은 3과 30의 비교가 나오고, 변수 칸의 return이 -1이 되어 a인 3이 앞에 남습니다. 3번째 단계에서는 "3430"이 "3034"보다 커서 return이 1이 되고, 30이 한 칸 뒤로 밀려납니다. 마지막 수 9는 8~11번째 단계에서 앞의 네 수를 모두 이기고 맨 앞까지 갑니다.

3 30 34 5 9
변수
a
–앞에 있던 수
b
–꺼낸 수
return
–
result
–

수를 문자열로 바꿔 한 줄로 세웠습니다. 맨 앞 3은 그대로 두고, 둘째 수 30을 꺼내 앞의 수와 비교합니다. "다음"을 눌러 보세요

  • 꺼내서 자리를 찾는 수 (b)
  • 비교하는 앞 수 (a)
  • 더 큰 이어 붙이기 · 완성된 순서
  • 순서를 정한 수
  • 아직 안 꺼낸 수
LeetCode 179 예제 2. 비교를 하나씩 보이려고 삽입 정렬로 돌렸고, 빌드할 때 실제로 실행해 기록한 단계입니다.

대표 문제 풀이

참고 풀이입니다. 비교 함수의 a, b는 위 시각화의 변수 칸과 같습니다.

var largestNumber = function (nums) {
  const strs = nums.map(String);

  strs.sort((a, b) => {
    if (a + b > b + a) return -1; // a를 앞에
    if (a + b < b + a) return 1; // b를 앞에
    return 0;
  });

  // 맨 앞이 "0"이면 모든 수가 0이다
  if (strs[0] === '0') return '0';
  return strs.join('');
};

sort가 어떤 두 수를 어떤 차례로 비교할지는 JavaScript 엔진이 정하므로 위 시각화의 비교 순서와 다를 수 있습니다. 하지만 비교 함수가 같으니 정렬을 마친 순서는 같습니다.

마지막의 "0" 검사는 [0, 0] 같은 입력 때문에 있습니다. 검사 없이 이어 붙이면 "00"이 나오는데, 수로 쓰면 "0"이어야 합니다. 0이 아닌 수 x는 x + "0"이 "0" + x보다 항상 커서 0보다 앞에 서므로, 정렬 뒤 맨 앞이 "0"이라면 나머지도 모두 0입니다.

비교는 O(n log n)번 일어납니다. 한 번의 비교에서 이어 붙이는 문자열은 nums[i] ≤ 10^9라 최대 20자이므로, 시간은 O(n log n)입니다. 문자열 배열 strs에 O(n) 공간을 씁니다.

자주 하는 실수

수의 크기나 사전 순으로 정렬합니다. 위에서 본 것처럼 [3, 30]에서 두 방법 모두 30을 앞에 세워 "303"을 만듭니다. 한 자리 수만 있는 입력에서는 두 방법 모두 맞는 답이 나오므로, 예제 1([10, 2] → "210")이나 [3, 30]처럼 자릿수가 다른 수로 확인해야 틀린 것이 드러납니다.

비교 함수가 참·거짓을 돌려줍니다. (a, b) => a + b < b + a는 true나 false를 돌려주는데, sort는 이 값을 1과 0으로 읽습니다. 음수가 한 번도 나오지 않아 “a를 앞에”라는 답을 줄 수 없고, Node.js에서 이 함수로 예제 2를 정렬하면 "9534330"이 아니라 "3303459"가 나옵니다. 반환값은 음수·양수·0 세 가지로 나눠 돌려줍니다.

모든 수가 0인 경우를 빠뜨립니다. [0, 0]에서 "00"을 돌려주면 오답입니다. 풀이의 strs[0] === '0' 검사가 이 경우를 막습니다.