[백준 11003/자바(Java)] 최솟값 찾기

최솟값 찾기

https://www.acmicpc.net/problem/11003

1단계 - 문제 분석하기

• 일정 범위 안에서 최솟값을 구하는 문제 → 슬라이딩 윈도우 + 정렬
• 일반적인 정렬의 시간 복잡도 nlog(n) → N과 L의 최대 범위가 5,000,000인 이 문제에서 정렬 사용 불가 → O(N)의 시간 복잡도로 해결해야 함.
• → 슬라이딩 윈도우를 덱(deque)으로 구한하여 정렬 효과를 볼 수 있음

덱의 구조

• 덱은 그림처럼 양 끝에서 데이터를 삽입하거나 삭제 가능한 자료구조이다.

2단계 - 손으로 풀어 보기

• 덱에서는 (인덱스, 숫자) 형태의 노드를 클래스로 구현하여 저장한다. 덱에서 노드를 제거하는 상황 설명을 위 해 (1,1)을 덱에 추가할 때, (2,5)를 덱에 추가할 때 필요한 탐색, 검사 과정 생략

덱의 과정1

• 이 상태에서 새 노드(3,2)가 덱에 저장. 여기부터 기존 덱에 있던 노드가 제거됨.

덱의 과정2

• 새 노드(3,2)가 저장될 때 덱 뒤에서부터 비교를 시작.
  • (2,5)는 (3,2)보다 숫자가 크므로 (2,5)는 덱에서 제거
  • (1,1)은 (3,2)보다 숫자가 작으므로 탐색을 멈추고 (3,2)를 덱에 저장
  • 결과를 보면 (2,5)가 덱에서 제거되어 덱에 있는 (1,1), (3,2) 순서로 노드가 오름차순 정렬되어 있음. → 덱을 이용하여 정렬 효과를 보는 방법
• 새 노드 추가. 인덱스 범위가 슬라이딩 윈도우를 벗어난 예

덱의 과정3

• 새 노드(4,3)은 덱 뒤에서부터 비교했을 때 (3,2)보다 숫자가 크므로 덱에 저장.
  • 인덱스 범위에 의해 덱 앞쪽의 노드가 제거됨.
  • (1,1), (3,2), (4,3)의 인덱스 범위는 1~4이므로 윈도우 범위인 3을 벗어남.
  • 최솟값은 윈도우 범위 내에서 찾기로 했으므로 (1,1)은 덱에서 제거.
  • 제거 후 최솟값을 출력하면 2
• 정리하면 숫자 비교, 윈도우 범위 계산이 끝난 덱에서 맨 앞에 있는 노드의 숫자를 출력하기만 하면 정답.

정답 출력 과정 정리

• 최초 (1,1)이 덱에 추가되면 비교 대상이 없고, 범위도 만족하므로 바로 1 출력
• (2,5)는 (1,1)과 숫자를 비교했을 때 더 크므로 탐색을 멈추고 덱에 추가. 인덱스 범위가 1~2여서 윈도우 범위를 만족하므로 다시 1을 출력
• (3,2)는 (2,5)와 숫자를 비교했을 때 더 작으므로 (2,5)를 덱에서 제거. (1,1)은 여전히 (3,2)보다 숫자가 작으므로 ㅌ마색을 멈추고 (3,2)를 덱에 저장. 덱의 상태는 (1,1), (3,2)가 되고, 인덱스 범위 1~3 역시 윈도우 범위를 만족하므로 다시 1을 출력

3단계 - 슈도코드 작성하기

N(데이터 개수) L(최솟값을 구하는 범위)
Deque<Node> mydeque(데이터를 담을 덱 자료구조)
배열 선언하기

for(N만큼 반복)
{
now(현재 데이터 값)
	덱의 마지막 위치에서부터 now보다 큰 값은 덱에서 제거
	덱의 마지막 위치에 now값 저장
	덱의 1번째 위치에서부터 L의 범위를 벗어난 값(now index-L <= index)을 덱에서 제거
	덱의 1번째 데이터 출력
}

덱에 저장할 노드 클래스 별도 생성
노드 클래스에는 index(자신의 위치), value(자신의 값) 담기

4단계 - 코드 구현하기

import javax.xml.soap.Node;
import java.util.*;
import java.io.*;

public class Main {
    public static final Scanner sc = new Scanner(System.in);
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //출력을 버퍼에 넣고 한 번에 출력하기 위해 BufferedWriter 사용
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        Deque<Node> mydeque = new LinkedList<>();
        for (int i = 0 ; i < N ; i++) {
            int now = Integer.parseInt(st.nextToken());
            //새로운 값이 들어올 때마다 정렬 대신 현재 수보다 큰 값을 덱에서 제거해 시간 복잡도를 줄임

            while (!mydeque.isEmpty() && mydeque.getLast().value > now) {
                mydeque.removeLast();
            }
            mydeque.addLast(new Node(now, i));
            //범위에서 벗어난 값은 덱 에서 제거
            if(mydeque.getFirst().index <= i - L) {
                mydeque.removeFirst();
            }
            bw.write(mydeque.getFirst().value + " ");
        }
        bw.flush();
        bw.close();
    }

    static class Node {
        public int value;
        public int index;

        Node(int value, int index) {
            this.value = value;
            this.index = index;
        }
    }
}