BOJ) 최솟값 찾기 (11003 번)

최솟값 찾기

11003번: 최솟값 찾기

 

슬라이딩 윈도우를 이용하는 문제로, N개의 수와 윈도의 크기 L이 주어진다.

D(i) = A(i-L+1) ~A(i) 중의 최솟값이라고 할 때, D에 저장되는 값을 출력하는 문제다.

 

즉, 자신의 위치에서 L칸 앞선 칸들 중 최솟값을 찾는 문제다.

처음에는 우선순위 큐로 시도하다가, 시간초과가 떴다.

아무래도 최악의 경우에는 O(N)이 추가돼서 그런 것 같다. (while을 통해 인덱스 범위를 검증하는 과정)

 

그래서 Deque를 이용했다.

처음 Deque에 입력할 때 부터, 큐의 가장 마지막 숫자와 비교하여 더 작은 경우 마지막에 입력하도록 설정했다.

또한, 가장 앞 부분을 확인해서 index를 벗어나면 Deque에서 빼주면서 답을 구했다.

 

더 좋은 방법은 없을까 생각하면서 이 문제를 맞은 사람들의 풀이를 살펴봤는데, ArrayDeque를 이용하고 있었다.

ArrayDeque는 Thread Safe를 보장하지 않지만, Stack과 LinkedList보다 빠르다고 설명한다.

또한, null 요소는 저장되지 않는다고 하는데, null이 오지 않는 조건에서는 Deque보다 좋은 자료구조라고 생각했다. (물론 멀티 쓰레드의 경우에는 조금 복잡해질 것이다.)

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class FindMinimum_11003 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int l = Integer.parseInt(st.nextToken());
        int[] numArr = new int[n];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            numArr[i] = Integer.parseInt(st.nextToken());
        }

        br.close();
        solution(numArr, n, l);
    }

    private static void solution(int[] numArr, int n, int l) {
        StringBuilder sb = new StringBuilder();
        final char SPACE = ' ';
        ArrayDeque<Node> deque = new ArrayDeque<>();

        for(int i=0; i<n; i++) {
            while(!deque.isEmpty() && deque.peekLast().num > numArr[i]) {
                deque.pollLast();
            }

            deque.offer(new Node(i, numArr[i]));
            if(deque.peek().index <= i-l) {
                deque.poll();
            }

            sb.append(deque.peek().num).append(SPACE);
        }
        System.out.println(sb.toString());
    }

    private static boolean isInRange(int target, int now, int l) {
        return target > now-l;
    }

    private static class Node implements Comparable<Node> {
        int index, num;

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

        @Override
        public int compareTo(Node node) {
            return this.num - node.num;
        }
    }
}