정렬

[10, 2, 33]을 비교 함수 없이 sort()에 넣으면 무슨 일이 벌어지는지 손으로 따라갑니다. 기본 규칙은 값을 문자열로 바꾼 뒤 글자를 앞에서부터 하나씩 비교합니다.

결과는 [10, 2, 33] — 하나도 정렬되지 않은 채 그대로입니다. 규칙 쪽지를 건네면 바로잡힙니다.

정렬 문제의 골격은 "원본 지키고 → 규칙 적고 → 기준을 이어 붙인다"입니다.

1. 원본이 필요하면 먼저 복사합니다 — sort()는 원본 배열을 그 자리에서 바꿉니다.

const sorted = [...arr].sort((a, b) => a - b); // 원본 arr은 그대로

2. 비교 함수를 적습니다 — 음수면 a가 앞, 양수면 b가 앞, 0이면 동률입니다.

arr.sort((a, b) => a - b); // 오름차순
arr.sort((a, b) => b - a); // 내림차순 (빼는 순서만 뒤집기)

3. 기준이 여러 개면 ||로 이어 붙입니다 — 앞 기준이 0(동률)일 때만 다음 기준으로 넘어갑니다.

b.score - a.score || a.late - b.late; // 점수 내림차순, 동점이면 지각 적은 순

전체 코드 — "점수 높은 순, 동점이면 지각 적은 순, 그래도 같으면 이름 사전순":

type Person = { name: string; score: number; late: number };
 
function solution(people: Person[]): string[] {
  // 1단계: 원본 보호를 위해 복사한 뒤 정렬
  const sorted = [...people].sort((a, b) =>
    // 2~3단계: 기준을 우선순위대로 이어 붙임
    b.score - a.score ||
    a.late - b.late ||
    a.name.localeCompare(b.name)
  );
  return sorted.map(p => p.name);
}

• 지문에 "단, ~가 같으면 ~순으로"라는 문장이 있으면 그 문장이 그대로 비교 함수 명세입니다. 순서대로 ||로 이어 붙이면 됩니다.
• 그리디 전처리: 마감 시간 순, 종료 시간 순, 가성비 순 — 그리디의 절반은 "무엇으로 정렬할지" 찾기입니다.
• 투 포인터/이진 탐색의 전제: 정렬돼 있어야 양끝 포인터와 이분 탐색이 성립합니다.
• 대표 문제 상황: 등수 매기기(다중 기준), 회의실 배정(종료 시간 순 정렬 후 그리디), 여러 수를 이어 붙여 가장 큰 수 만들기.

JS/TS sort()의 함정 두 가지 — 이것부터 몸에 배어야 합니다.

[10, 2, 33].sort();                // [10, 2, 33] 잘못된 결과 — 기본은 문자열 비교
[10, 2, 33].sort((a, b) => a - b); // [2, 10, 33] 숫자 오름차순

1. 비교 함수 없이 숫자를 정렬하면 문자열로 비교됩니다. 반드시 (a, b) => a - b를 넘기세요.
2. sort()는 원본을 변형합니다. 원본이 필요하면 [...arr].sort(...)로 복사 후 정렬합니다.

비교 함수 설계 — 코테의 핵심

// 점수 내림차순 → 동점이면 지각 횟수 오름차순 → 그래도 같으면 이름 사전순
people.sort((a, b) =>
  b.score - a.score ||
  a.late - b.late ||
  a.name.localeCompare(b.name)
);

||가 앞 기준이 0(동률)일 때만 다음 기준으로 넘어가는 트릭입니다. 한국 코테 단골 패턴이니 손에 익히세요.

// 문자열 이어붙이기 비교 — "가장 큰 수 만들기"류
nums.sort((a, b) => Number(`${b}${a}`) - Number(`${a}${b}`));

• 숫자 배열에 비교 함수를 빼먹음 (위 함정 1).

nums.sort();                 // 잘못: 문자열 비교라 [10, 2, 33] 그대로
nums.sort((a, b) => a - b);  // 고침

• 비교 함수가 일관성 없음 — 같은 쌍에 대해 호출마다 다른 부호를 반환하면 결과가 미정의입니다. 예: 부동소수점 계산 결과를 비교에 바로 사용.

arr.sort((a, b) => Math.random() - 0.5);   // 잘못: 부를 때마다 답이 달라짐
arr.sort((a, b) => a.ratio - b.ratio);     // 고침: 미리 계산해 둔 값으로 일관되게

• localeCompare를 써야 할 한글/문자열 비교에 a - b류 산술을 시도.

names.sort((a, b) => a - b);                 // 잘못: 문자열끼리 빼면 NaN
names.sort((a, b) => a.localeCompare(b));    // 고침

• 원본이 필요한데 그 자리에서 정렬해 버림.

const sorted = arr.sort((a, b) => a - b);  // 잘못: arr도 함께 바뀜
const sorted2 = [...arr].sort((a, b) => a - b); // 고침

• 안정 정렬 가정: JS의 sort는 안정(stable)이 보장되지만(ES2019+), 동률 기준을 비교 함수에 명시하는 편이 언제나 안전합니다.

• 시각화의 버블 정렬: O(N²)라 실전용은 아니지만, "비교와 교환"이라는 정렬의 원리를 눈으로 이해하기에 가장 좋습니다.
• 왜 O(N log N)인가: 비교만으로 순서를 정하는 정렬은 이론적으로 O(N log N)보다 빠를 수 없습니다. N개의 순서 조합이 N!가지이고 비교 한 번이 경우의 수를 절반으로 줄이므로, 필요한 비교 횟수가 log(N!) ≈ N log N이기 때문입니다.
• 엔진 내부: V8의 sort는 TimSort(병합 정렬 + 삽입 정렬 혼합)로 구현되어 있습니다. 이미 정렬된 구간(run)을 찾아 재활용하므로, 부분적으로 정렬된 입력에서는 O(N)에 가깝게 동작합니다.
• 비교 없이 정렬하기: 값의 범위가 좁으면(예: 0~1000의 정수) 계수 정렬(counting sort)로 O(N + K)에 끝낼 수 있습니다. 값을 인덱스로 삼아 개수만 세는 방식이며, 위 O(N log N) 하한은 비교 기반 정렬에만 적용되므로 모순이 아닙니다.
• 부동소수점 비교: a - b가 아주 작은 값이면 부호가 계산 오차에 좌우될 수 있습니다. 정수로 환산할 수 있으면 환산하고(예: 금액을 원 단위 정수로), 아니면 허용 오차를 두고 Math.abs(a - b) < 1e-9 ? 0 : a - b 형태로 동률을 명시합니다.

시각화로 "비교 → 교환 → 확정"의 리듬을 본 뒤, 기본 정렬 문제 → 커스텀 비교(다중 키) → 정렬+그리디 조합 순으로 푸세요.