연속된 배열 원소 감지 - 슬라이딩 윈도우

백준 1337번 풀이를 기반으로 정리

---

핵심 아이디어

"정렬된 배열에서 길이 N짜리 연속 구간에 원소가 최대 몇 개 들어올 수 있는가?"

• 최소 연산 횟수 = N - 윈도우 안에 들어오는 최대 원소 수
• 원소를 추가/삭제하는 게 아니라, 윈도우(범위)를 슬라이딩하며 탐색

---

슬라이딩 윈도우 패턴

조건

• 배열이 정렬되어 있어야 함
• 윈도우 유효 조건: arr[right] - arr[left] < N

동작 방식

정렬된 배열: [1, 2, 3, 10, 20]  (N = 5)

right=0: [1]            차이=0  < 5  → count=1
right=1: [1,2]          차이=1  < 5  → count=2
right=2: [1,2,3]        차이=2  < 5  → count=3
right=3: [1,2,3,10]     차이=9  >= 5 → left를 당김
         [2,3,10]       차이=8  >= 5 → left를 당김
         [3,10]         차이=7  >= 5 → left를 당김
         [10]           차이=0  < 5  → count=1
right=4: [10,20]        차이=10 >= 5 → left를 당김
         [20]           차이=0  < 5  → count=1

maxCount = 3
정답 = 5 - 3 = 2

코드 (백준 1337 기준)

static int solve(int[] arr, int N) {
    Arrays.sort(arr);

    int left = 0;
    int maxCount = 1;

    for (int right = 0; right < arr.length; right++) {
        while (arr[right] - arr[left] >= N) {
            left++;
        }
        maxCount = Math.max(maxCount, right - left + 1);
    }

    return N - maxCount;
}

---

왜 중복을 제거하지 않아도 되는가?

중복 원소가 있으면 윈도우 조건 arr[right] - arr[left] >= N에서
차이가 커지지 않아 left가 당겨지지 않는다.

그러나 중복 원소는 연속된 배열에 2개 이상 존재할 수 없으므로,
결국 중복이 포함된 윈도우는 정답이 될 수 없다.

→ 이 문제의 입력(N=5, 값 범위 제한)에서는 중복 제거 없이도 통과되지만,
일반적인 경우엔 중복 제거를 전처리로 추가하는 것이 안전하다.

// 안전한 전처리 버전
int[] arr = Arrays.stream(arr)
                  .distinct()
                  .sorted()
                  .toArray();

---

언제 슬라이딩 윈도우를 쓰는가?

---

관련 풀이 패턴 비교

패턴 1. 정렬 + 인접 비교

// "다음 원소 = 현재 원소 + 1" 인지 확인
for (int i = 1; i < arr.length; i++) {
    if (arr[i] == arr[i-1] + 1) count++;
    else count = 1;
}

패턴 2. 슬라이딩 윈도우 ← 1337번

// "윈도우 범위 안에 원소가 최대 몇 개인지" 확인
while (arr[right] - arr[left] >= N) left++;
maxCount = Math.max(maxCount, right - left + 1);

패턴 3. HashSet (정렬 없이 O(N))

// "연속 구간의 시작점"에서만 탐색
if (!set.contains(val - 1)) {
    while (set.contains(++cur)) count++;
}