[코딩테스트] 백준 11003 자바

백준 11003

백준 11003 문제

해당 문제는 이동하는 주어진 범위 내에서 최솟값을 구하는 문제이므로 슬라이딩 윈도우 알고리즘을 사용하면 되는 문제인데, 최솟값을 구하기 위해 정렬을 사용하면 시간 복잡도 O(n2 × log n)이 되기 때문에 시간 제한을 초과하게 된다.

하지만 슬라이딩 윈도우를 덱(deque)로 구현하면 정렬 효과를 얻을 수 있어 시간 복잡도 O(n)으로 해결이 가능하다.

import java.io.*;
import java.util.*;

public class Boj11003 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // 출력을 버퍼에 넣고 한 번에 출력하기 위해 BufferedWriter 사용
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 데이터 개수
        int l = Integer.parseInt(st.nextToken()); // 최솟값을 구하는 범위
        Deque<Node> deque = new LinkedList<>(); // 데이터를 담을 덱 자료구조

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) { // n만큼 반복
            int now = Integer.parseInt(st.nextToken()); // 현재 데이터 값

            // 새로운 값이 들어올 때마다 정렬 대신 현재 수보다 큰 값을 덱에서 제거해 시간 복잡도를 줄임
            while (!deque.isEmpty() && deque.getLast().value > now) { // 덱의 마지막 위치에서부터 now보다 큰 값은
                deque.removeLast(); // 덱에서 제거
            }

            deque.addLast(new Node(i, now)); // 덱의 마지막 위치에 now값 저장하기

            if (deque.getFirst().index <= i - l) { // 덱의 첫 번째 노드의 index가 l의 범위를 벗어난 값(index <= i - l)이면
                deque.removeFirst(); // 덱에서 제거
            }

            bw.write(deque.getFirst().value + " "); // 덱의 첫 번째 데이터 출력하기
        }

        bw.flush();
        bw.close();
        br.close();
    }

    static class Node { // 덱에 저장할 노드 클래스 별도 생성
        public int index; // 자신의 위치
        public int value; // 자신의 값

        public Node(int index, int value) { // 생성자로 받아서 저장
            this.index = index;
            this.value = value;
        }
    }
}

풀이

1. 덱에 저장할 노드 클래스를 static class로 별도 생성한다.
   • 노드 클래스는 자신의 위치를 가리키는 index 멤버와 자신의 값을 가리키는 value 멤버를 갖는다.
2. 출력을 버퍼에 넣고 한 번에 출력하기 위해 BufferedWriter 사용한다.
3. 데이터 개수를 n으로 받는다.
4. 최솟값을 구하는 범위를 l로 받는다.
5. 데이터를 담을 덱 자료구조 deque를 생성한다.
6. n만큼 반복하며 새로운 값이 들어올 때마다 정렬 대신 현재 수보다 큰 값을 덱에서 제거해 정렬 효과와 함께 시간 복잡도를 줄인다.
   1. Integer.parseInt(st.nextToken())를 통해 현재 값을 now로 받는다.
   2. while (!deque.isEmpty() && deque.getLast().value > now)로 덱의 마지막 위치에서부터 now보다 큰 값은 deque.removeLast()로 덱에서 제거한다.
   3. deque.addLast(new Node(i, now))로 덱의 마지막 위치에 now값을 저장한다.
   4. 덱의 첫 번째 노드의 index가 l의 범위를 벗어난 값(index <= i - l)이면 deque.removeFirst()로 덱에서 제거한다.
   5. bw.write(deque.getFirst().value + " ")로 덱의 첫 번째 값을 출력한다.
7. 자원을 반납한다.