[코딩 테스트] 2026-03-25 — 슬라이딩 윈도우 최댓값

오늘의 문제 선정 이유

 

실시간 로그, 스트리밍 데이터, 추천 피드처럼 구간별 최댓값을 빠르게 구하는 문제는 최근 서비스 개발 흐름과도 맞고, 코딩 테스트에서도 자주 나옵니다.

문제 설명

당신은 영상 플랫폼의 실시간 인기 점수 배열 scores를 분석하고 있습니다.
이 배열에서 길이 k인 연속 구간을 왼쪽부터 한 칸씩 이동시키며, 각 구간의 최댓값을 구하려고 합니다.

예를 들어 scores = [4, 2, 12, 3, 8, 7], k = 3이라면 가능한 구간은 다음과 같습니다.

• [4, 2, 12]의 최댓값은 12

 

• [2, 12, 3]의 최댓값은 12

 

• [12, 3, 8]의 최댓값은 12

 

• [3, 8, 7]의 최댓값은 8

따라서 결과는 [12, 12, 12, 8]입니다.

배열 scores와 정수 k가 주어질 때, 각 슬라이딩 윈도우의 최댓값을 순서대로 담은 배열을 반환하는 함수를 작성하세요.

입출력 예시

[text]입력: scores = [4, 2, 12, 3, 8, 7], k = 3
출력: [12, 12, 12, 8]
설명: 길이 3인 각 연속 구간의 최댓값을 왼쪽부터 구한 결과입니다.

[text]입력: scores = [9, 9, 5, 1, 6], k = 2
출력: [9, 9, 5, 6]
설명:
[9, 9] -> 9
[9, 5] -> 9
[5, 1] -> 5
[1, 6] -> 6

[text]입력: scores = [1, 3, 1, 2, 0, 5], k = 4
출력: [3, 3, 5]
설명:
[1, 3, 1, 2] -> 3
[3, 1, 2, 0] -> 3
[1, 2, 0, 5] -> 5

제약 조건

• 1 <= len(scores) <= 200,000

 

• -10^9 <= scores[i] <= 10^9

 

• 1 <= k <= len(scores)

 

• 시간 제한: O(n log n) 이내 통과 가능, O(n) 풀이 권장

 

• 같은 값이 여러 번 등장할 수 있음

풀이 접근법

핵심 아이디어

이 문제는 각 구간마다 최댓값을 다시 찾으면 O(nk)가 되어 비효율적입니다.
그래서 deque에 "최댓값 후보가 될 수 있는 인덱스"만 남겨 두고, 항상 앞쪽에 현재 윈도우의 최댓값이 오도록 유지합니다.

값이 작은 원소는 뒤에서 제거해도 됩니다. 어차피 더 큰 값이 뒤에 들어왔기 때문에, 앞으로 최댓값이 될 가능성이 없기 때문입니다.

단계별 풀이 과정

1. deque에는 값이 아니라 인덱스를 저장합니다.
2. 새 원소 scores[i]를 넣기 전에, 현재 값보다 작거나 같은 인덱스를 deque 뒤에서 제거합니다.
3. 현재 인덱스 i를 deque 뒤에 추가합니다.
4. deque 앞쪽 인덱스가 현재 윈도우 범위를 벗어났다면 제거합니다.
5. i >= k - 1부터는 윈도우가 완성된 상태이므로, scores[deque[0]]를 결과에 추가합니다.

코드 풀이

Python

 

[python]from collections import deque

def max_sliding_window(scores, k):
    dq = deque()  # 최댓값 후보 인덱스를 저장
    result = []

    for i in range(len(scores)):
        # 현재 값보다 작거나 같은 값은 앞으로 최댓값이 될 수 없으므로 제거
        while dq and scores[dq[-1]] <= scores[i]:
            dq.pop()

        dq.append(i)

        # 윈도우 왼쪽 범위를 벗어난 인덱스 제거
        if dq[0] <= i - k:
            dq.popleft()

        # 윈도우가 완성된 시점부터 결과 기록
        if i >= k - 1:
            result.append(scores[dq[0]])

    return result


# 예시 실행
print(max_sliding_window([4, 2, 12, 3, 8, 7], 3))   # [12, 12, 12, 8]
print(max_sliding_window([9, 9, 5, 1, 6], 2))       # [9, 9, 5, 6]
print(max_sliding_window([1, 3, 1, 2, 0, 5], 4))    # [3, 3, 5]

JavaScript

 

[javascript]function maxSlidingWindow(scores, k) {
  const dq = []; // 인덱스를 저장하는 deque 역할
  let head = 0;
  const result = [];

  for (let i = 0; i < scores.length; i++) {
    // 현재 값보다 작거나 같은 값은 제거
    while (dq.length > head && scores[dq[dq.length - 1]] <= scores[i]) {
      dq.pop();
    }

    dq.push(i);

    // 윈도우 범위를 벗어난 인덱스 제거
    if (dq[head] <= i - k) {
      head++;
    }

    // 윈도우가 완성되면 최댓값 기록
    if (i >= k - 1) {
      result.push(scores[dq[head]]);
    }
  }

  return result;
}

// 예시 실행
console.log(maxSlidingWindow([4, 2, 12, 3, 8, 7], 3)); // [12, 12, 12, 8]
console.log(maxSlidingWindow([9, 9, 5, 1, 6], 2));     // [9, 9, 5, 6]
console.log(maxSlidingWindow([1, 3, 1, 2, 0, 5], 4));  // [3, 3, 5]

시간·공간 복잡도

• 시간 복잡도: O(n) — 각 인덱스가 deque에 한 번 들어가고 한 번만 나옵니다.

 

• 공간 복잡도: O(k) — deque에는 현재 윈도우 후보들만 저장됩니다.

틀리기 쉬운 포인트

• deque에 값을 저장하면 범위에서 빠진 원소를 정확히 제거하기 어렵습니다. 인덱스를 저장해야 합니다.

 

• 뒤에서 제거할 때 <=와 < 차이를 헷갈리기 쉽습니다. 같은 값이 들어올 때도 최신 인덱스를 남기려면 <=가 더 안전합니다.

 

• 윈도우 범위 체크를 i - k 기준으로 해야 합니다. i - k + 1과 혼동하면 한 칸 늦거나 빨리 제거할 수 있습니다.

유사 문제 패턴

• 슬라이딩 윈도우 최솟값: 비교 방향만 바꾸면 같은 방식으로 풀이할 수 있습니다.

 

• 고정 길이 구간의 조건 만족 개수 구하기: 빈도 배열, 해시맵과 함께 슬라이딩 윈도우 패턴을 연습할 수 있습니다.

 

• Deque를 이용한 우선순위 유지 문제: 구간 최대/최소, 후보 압축, 단조 큐 패턴으로 이어집니다.