먼저 정렬하면 해법이 열리는 이유

정렬만으로 문제가 해결되는 경우는 드물지만, 정렬은 진짜 핵심 아이디어를 준비해 줍니다. 순서를 정하면 복잡한 배열이 활용할 수 있는 구조로 바뀝니다.

데이터가 정렬되면 두 포인터가 양쪽 끝에서 훑어갑니다. 목표 합을 이루는 쌍을 찾는 비용이 O(n²)에서 O(n)으로 줄어듭니다.

정렬된 배열은 이진 탐색으로 가는 관문입니다. 정렬되어 있으면 O(log n)에 값이나 삽입 위치를 찾을 수 있습니다.

많은 탐욕적 알고리즘의 증명에서는 가장 작은 것을 선택하거나 가장 일찍 끝나는 것을 먼저 처리하라고 합니다. 해당 필드로 정렬하면 올바른 선택을 바로 확인할 수 있습니다.

정렬한 뒤에는 같은 항목이 서로 옆에 놓입니다. 그러면 추가 메모리 없이 한 번만 훑어서 중복을 찾거나 셀 수 있습니다.

구간을 병합하거나 일정을 정하려면 먼저 시작 시간을 기준으로 정렬합니다. 그러면 왼쪽에서 오른쪽으로 훑으면서 겹치는 부분을 깔끔하게 처리할 수 있습니다.

정렬한 뒤 가운데 있는 원소가 중앙값이며, 이웃한 원소 사이의 간격도 분명해집니다. 많은 거리 문제에서 이 성질을 활용합니다.

정렬은 O(n log n)의 비용을 추가하지만, 정렬로 가능해지는 작업에 비하면 대개 저렴합니다. 이를 활용하기 전에 시간 제한에 맞는지 확인하세요.

정렬하면 위치가 뒤섞입니다. 답에 원래 인덱스가 필요하다면 값과 인덱스를 쌍으로 묶어 sort하여 원래 위치를 복원할 수 있게 하세요.

막혔을 때는 정렬하면 문제가 단순해지는지 자문해 보세요. 그렇다면 먼저 sort하고 두 포인터, 탐욕적 알고리즘 또는 이진 탐색으로 이어지는 풀이가 자주 나타납니다.

실력 있는 문제 해결자는 기본 실험으로 정렬을 일찍 시도합니다. 추가하기도 저렴하고 전체 풀이를 드러내는 경우가 많습니다.

배열을 정렬했지만 나중에 입력에서 각 원소의 위치가 필요합니다.

정렬은 두 포인터, 이진 탐색, 탐욕적 알고리즘, 중복 제거, 구간 훑기를 가능하게 합니다. 비용을 예산에 반영하고 필요할 때는 인덱스를 보존하세요. 🚀