[백준] 11003_최솟값 찾기 - JAVA

백준_11003

11003번: 최솟값 찾기

 

덱(deque)

위 문제는 슬라이딩 윈도우와 정렬을 사용하면 될 것 같지만 정렬은 nlog(n)의 시간 복잡도를 가지고, N과 L의 범위가 5,000,000인 이 문제에서는 정렬을 사용할 수 없다. O(n)의 시간 복잡도로 해결해야 한다. 정렬 대신 슬라이딩 윈도우와 덱(deque)이란 자료구조를 사용하면 이 문제를 풀 수 있다.

출처 : https://soft.plusblog.co.kr/24

덱은 양 끝에서 데이터를 삽입하거나 삭제할 수 있는 자료구조이다. 왼쪽에서는 addFirst(), removeFirst() 함수가 삽입, 삭제 역할을 하고, 오른쪽에서는 addLast(), removeLast() 함수가 삽입, 삭제 역할을 한다.

덱은 (값, 인덱스) 형태의 노드를 클래스로 구현하여 저장한다. 새로운 노드가 저장될 때 기존 덱이 가지고 있는 뒤에 있던 노드부터 차례로 비교를 시작한다. 만약 기존에 있던 노드보다 새로운 노드의 값이 더 작다면 기존에 있던 노드는 덱에서 제거(removeLast) 된다. 이런식으로 비교를 반복하다가 최솟값을 찾을 때, 덱의 제일 앞에 있는 노드를 선택해 반환하면 된다. 즉, 덱 처음에 있는 노드가 최솟값이다.

 

코드

import java.io.*;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;

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 bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        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();
            }
            sb.append(myDeque.getFirst().value).append(" ");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

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

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

 

제출 결과

영겁의 시간 끝에 드디어 통과되었다. 덱이라는 자료구조 자체를 처음 접해봤어서 내 힘으로는 도저히 풀 수 없는 문제라 코드를 처음부터 보면서 코드를 공부한다는 느낌으로 풀었다. 그런데 교재에 나와있는 정답이 시간초과가 뜨는 바람에 더 이것저것 찾아보았다. 내가 직접 푼 문제면 금방 해결했었을텐데.. 아무튼 교재에서는 최솟값을 붙이는 과정에서 '최솟값 + " "' 이런 식으로 코드가 작성되어 있었다. 그래서 StringBuilder로 코드를 수정했더니 통과되었다! 로직 자체는 막 어렵지 않은 거 같은데 처음 보는 클래스들이 너무 많다; 공부 열심히 더 해야지.