[Do it! 알고리즘 코딩 테스트 자바] 슬라이딩 윈도우와 Deque - 백준 11003(5일차)

슬라이딩 윈도우: 2개의 포인터로 범위를 지정한 후 범위를 유지한 채로 이동

핵심 원리

- 업데이트할 때 새로 추가하는 문자열과 제거되는 문자열만 확인

- 배열의 길이만큼만 탐색 진행

- 시간 복잡도: O(n)

 

주요 사용처: 연속된 데이터 구간의 합, 최댓값/최솟값, 부분 문자열 검색 등.

 

---

Deque(Double-Ended Queue): 양쪽 끝에서 모두 데이터의 삽입과 삭제가 가능한 

핵심 원리

- 먼저 들어온 것이 먼저 나가는 큐(FIFO)의 특성과 나중에 들어온 것이 먼저 나가는 스택(LIFO)의 특성을 모두 가짐.

- 데이터의 앞(Front/Head)과 뒤(Rear/Tail) 어디서든 자유롭게 넣고 뺄 수 있어 유연함.

 

슬라이딩 윈도우와의 시너지: 윈도우가 이동할 때, '빠져나가야 할 오래된 값'은 앞에서 빼고(removeFirst), '새로 들어오는 값'은 뒤에 넣으면서(addLast) 윈도우의 상태를 효율적으로 관리하기에 최적화.

 

선언 방식

Deque<Integer> deque = new ArrayDeque<>();

 

주요 메서드

Deque의 함수는 크게 예외(Exception)를 발생시키는 함수와 값(null 또는 false)을 반환하는 함수로 나뉨.

코딩 테스트에서는 안전한 조회를 위해 주로 후자(peek, poll 등)를 많이 사용함.

 

[앞(Front/Head)에서 조작]

• addFirst(e) / offerFirst(e): 덱의 맨 앞에 데이터를 삽입합니다.
• removeFirst() / pollFirst(): 덱의 맨 앞 데이터를 빼내고(삭제) 반환합니다. (poll은 비어있으면 null 반환)
• getFirst() / peekFirst(): 덱의 맨 앞 데이터를 삭제하지 않고 확인만 합니다. (peek은 비어있으면 null 반환)

[뒤(Rear/Tail)에서 조작]

• addLast(e) / offerLast(e): 덱의 맨 뒤에 데이터를 삽입합니다. (일반 큐의 add와 동일)
• removeLast() / pollLast(): 덱의 맨 뒤 데이터를 빼내고(삭제) 반환합니다.
• getLast() / peekLast(): 덱의 맨 뒤 데이터를 삭제하지 않고 확인만 합니다.

[기타 유용한 함수]

• isEmpty(): 덱이 비어있는지 확인합니다. (비어있으면 true)
• size(): 덱에 들어있는 데이터의 개수를 반환합니다.
• clear(): 덱 안의 모든 데이터를 비웁니다.

 

---

백준 11003번(최솟값 찾기)

1. 주요 오개념 및 시행착오 (Pain Point)

• 인덱스 범위 해석의 오류: 윈도우 시작 지점인 i-L+1이 음수일 때, '존재하지 않는 값은 무시한다'는 문제 조건을 잘못 파악함. 배열을 순환 구조로 오인하여 전체 크기 N을 더하는 등 임의의 인덱스 보정 로직을 추가해 결과 개수 불일치 발생.
• 최솟값 갱신 로직의 한계: 단순히 현재 최솟값 변수(min)와 새로 들어오는 값을 비교하는 방식 적용. 윈도우에서 빠져나가는 값이 현재 최솟값과 같을 때, 다음 최솟값을 찾기 위해 반복문 내부에서 다시 전체 범위를 탐색하는 O(N * L)의 비효율적 로직 구현.
• 자료구조 부재로 인한 시야 제한: Deque 구조를 알지 못해, 조건에 맞지 않는 값을 제거하며 탐색 범위 자체를 줄여나가는 '슬라이딩 윈도우 최적화' 방식을 떠올리지 못함.

2. 핵심 원리 및 수학적 근거 (Logic & Math)

• 단조 큐(Monotonic Queue) 원리: Deque 내부를 항상 오름차순 상태로 유지. 새로 들어올 값보다 기존에 윈도우 안에 있던 큰 값들은 앞으로 윈도우 내에서 절대 최솟값이 될 수 없음을 수학적으로 보장.
• 가치 없는 데이터의 선제적 파기: 나보다 늦게 들어왔으면서 값도 작은 원소가 등장하면, 기존의 큰 원소는 생명력을 완전히 상실함. 이를 즉시 버림으로써 윈도우 내 탐색 대상을 최소화.
• 분할 상환 분석(Amortized Analysis)에 따른 시간 복잡도: 반복문 안에 while 문이 존재하나, 배열의 모든 원소는 Deque에 최대 한 번 삽입(push)되고 최대 한 번 삭제(pop)됨. 총 연산 횟수가 2N에 수렴하므로 전체 시간 복잡도 O(N) 보장.

3. 설계 통찰

• 값 대신 인덱스 저장: Deque에 값 자체를 넣는 대신 인덱스를 저장. 이를 통해 윈도우 유효 범위(i-L+1) 이탈 여부 검사와 원본 배열(num_array)을 통한 최솟값 조회를 동시에 해결하는 구조적 이점 확보.
• 객체 생성 억제를 통한 성능 극대화: Node(인덱스, 값) 클래스를 만들어 매 반복마다 객체를 생성(new)하는 대신, 별도의 원본 배열과 인덱스만 담는 Deque를 조합하여 가비지 컬렉터(GC) 부하 및 메모리 오버헤드 원천 차단.
• 사고의 패러다임 전환: 특정 조건에서만 동작하는 분기문(if-else) 중심의 예외 처리 로직에서 벗어나, 규칙에 따라 불필요한 값을 지속적으로 덜어내는 필터링 중심의 로직으로 설계 관점 이동.

4. 구현상의 유의점 (Implementation Wisdom)

• Deque 데이터 처리 순서 엄수:
  1. 새 값보다 큰 값들은 Deque의 뒤(last)에서 모두 제거.
  2. 현재 값의 인덱스를 Deque의 뒤(last)에 추가.
  3. 윈도우 범위를 벗어난 인덱스는 Deque의 앞(first)에서 제거.
  4. 맨 앞(first)에 남은 인덱스가 가리키는 원본 배열 값이 현재 윈도우의 최솟값.
• 동일 값 처리 방식: 새로 들어오는 값과 Deque 내부의 값이 같을 때도 기존 값을 제거하고 새 인덱스로 교체하는 것이 윈도우 내 생존 기간을 늘리는 측면에서 유리.
• 대용량 I/O 처리 유지: 500만 개의 데이터 입출력 시 병목 현상을 막기 위해 BufferedReader와 BufferedWriter, StringTokenizer 구조 유지 필수.