정렬 후 인접 비교

정렬을 한 뒤 인접한 두 원소만 비교해서, 모든 쌍을 검사하지 않고도 특정 관계를 찾아내는 알고리즘 패턴입니다.

왜 인접만 봐도 되는가?

정렬의 핵심 성질:
"관계가 있는 두 원소"가 정렬 후 반드시 이웃이 된다.

→ 그 관계를 찾기 위해 모든 쌍을 비교(O(n²))할 필요 없이
   인접한 쌍만 비교(O(n))하면 충분.

전체 비용은 정렬(O(n log n)) + 인접 비교(O(n)) = O(n log n).

활용 가능한 관계들

찾고 싶은 것정렬 기준인접 비교 조건
중복 원소값 오름차순arr[i] == arr[i+1]
가장 가까운 두 수값 오름차순min(arr[i+1] - arr[i])
문자열 접두사사전식arr[i+1].startsWith(arr[i])
겹치는 구간시작점 오름차순prev.end > next.start
연속된 정수값 오름차순arr[i+1] - arr[i] == 1

패턴 1: 중복 검사

int[] arr = {3, 1, 2, 3, 4};
Arrays.sort(arr);
// [1, 2, 3, 3, 4]

for (int i = 1; i < arr.length; i++) {
    if (arr[i] == arr[i-1]) {
        return true;   // 중복 발견
    }
}
return false;

[ 단계별 추적 ]

[1, 2, 3, 3, 4]
 ↑ ↑                       i=1: 1 != 2
    ↑ ↑                    i=2: 2 != 3
       ↑ ↑                 i=3: 3 == 3 → 중복!

해시셋(O(n))보다 약간 느리지만 공간 O(1) 인-플레이스.

패턴 2: 가장 가까운 두 수

int[] arr = {30, 10, 50, 11, 100};
Arrays.sort(arr);
// [10, 11, 30, 50, 100]

int minDiff = Integer.MAX_VALUE;
for (int i = 1; i < arr.length; i++) {
    minDiff = Math.min(minDiff, arr[i] - arr[i-1]);
}
// minDiff = 1   ← (10, 11)

[ 단계별 추적 ]

[10, 11, 30, 50, 100]
  ↑   ↑                  diff = 1   ← 최소
       ↑   ↑             diff = 19
            ↑   ↑        diff = 20
                ↑   ↑    diff = 50

→ 모든 쌍 O(n²) 비교 안 해도 정답

왜 인접만 봐도 충분한가? 정렬된 배열에서 어떤 두 수의 차이는 그 사이에 있는 인접 차이들의 합 이상. 따라서 최소 차이는 반드시 인접한 쌍에서 나옴.

패턴 3: 문자열 접두사 검사 (전화번호 목록)

String[] phoneBook = {"119", "97674223", "1195524421"};
Arrays.sort(phoneBook);
// ["119", "1195524421", "97674223"]

for (int i = 0; i < phoneBook.length - 1; i++) {
    if (phoneBook[i+1].startsWith(phoneBook[i])) {
        return false;
    }
}
return true;

[ 단계별 추적 ]

정렬 후: ["119", "1195524421", "97674223"]
           ↑       ↑
           └───────┴─ "1195524421".startsWith("119") → true → return false

왜 인접만 봐도 충분한가? 사전식 정렬에서, 어떤 문자열 A가 B의 접두사라면 A 바로 뒤에 B가 위치한다. 그 사이에 끼어드는 문자열 C가 있을 수 없음(C도 A를 접두사로 가져야 하므로).

직관:

A = "119"
B = "1195524421"

만약 정렬에서 A와 B 사이에 C가 끼어든다면?
A < C < B 이려면 C도 "119..."로 시작해야 함.
그렇지 않으면 C는 A보다 작거나(불가능) B보다 큼(불가능).

→ A와 B는 정렬 후 항상 인접

대안으로 HashMap 풀이도 가능:

패턴 4: 구간 겹침 검사

int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};

// 시작점 기준 정렬
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
// 이미 정렬됨: [[1,3], [2,6], [8,10], [15,18]]

for (int i = 1; i < intervals.length; i++) {
    if (intervals[i-1][1] > intervals[i][0]) {
        // 겹침 발견 (이전 끝 > 다음 시작)
    }
}

[ 단계별 추적 ]

[1, 3]  [2, 6]  [8, 10]  [15, 18]
 끝=3   시작=2              ← 3 > 2 → 겹침!
 끝=6   시작=8              ← 6 < 8
 끝=10  시작=15             ← 10 < 15

→ (1,3)과 (2,6) 겹침

이 패턴의 확장으로 회의실 배정 / 작업 스케줄링 / 구간 병합 같은 그리디 문제가 풀린다.

시간복잡도 비교

접근법시간공간
모든 쌍 비교 (naive)O(n²)O(1)
해시 기반O(n)O(n)
정렬 후 인접 비교O(n log n)O(1)

해시가 가장 빠르지만, 인-플레이스가 필요하거나 입력 자체가 정렬된 상태로 들어올 때 정렬 후 인접 비교가 빛난다.

핵심 정리

이 패턴은 "관계 있는 원소가 정렬 후 이웃이 된다" 는 정렬의 성질을 활용해서, O(n²) 비교를 O(n log n)으로 줄이는 기법입니다. 중복 검사, 가장 가까운 두 수, 문자열 접두사, 구간 겹침 등 다양한 문제에 적용되며, 해시보다 느리지만 공간 O(1) 이고 코드가 간결한 게 장점입니다. 적용 가능 여부를 판단하려면 "정렬했을 때 답이 인접한 두 원소 사이에서 발견될 수 있는가?"를 먼저 검증해야 합니다.

CSLOG에서 보기