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

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

11003번: 최솟값 찾기

---

2. 내가 푼 방법

Deque 자료형을 알고 있었기 때문에, 금방 구현할 수 있는 문제였다. Deque는 스택과 큐 기능이 모두 들어간 양방향 자료형이며, 양쪽 끝 연산에 특화되어 있기 때문에 O(1) 시간복잡도로 처리할 수 있다.

 

이 문제는 가장 나중에 넣는 값이 항상 더 큰 값만 가지는 게 핵심이다. 그래야만 Deque 머리 부분에서 최소 값을 뽑아낼 수 있기 때문이다. 따라서 Deque에 저장된 꼬리 값을 비교함과 동시에 Deque 머리에 저장된 인덱스가 D 범위에 해당하는지 확인하면 된다.

 

나는 Deque에 인덱스가 저장되도록 코드를 작성했기 때문에, 값을 가져올 때 그때그때 인덱스에 접근했다,

for (int i = 0; i < N; i++) {
    while (!dq.isEmpty() && dq.peekFirst() < i - L + 1) {
        dq.pollFirst();
    }
    while (!dq.isEmpty() && arr[dq.peekLast()] >= arr[i]) {
        dq.pollLast();
    }

    dq.offerLast(i);
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B11003.java

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

class Main {
    static int N, L;
    static int[] arr;

    public static void main (String[] args) throws IOException {
        solution();
    }

    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Deque<Integer> dq = new ArrayDeque<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        arr = new int[N];

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

        for (int i = 0; i < N; i++) {
            while (!dq.isEmpty() && dq.peekFirst() < i - L + 1) {
                dq.pollFirst();
            }
            while (!dq.isEmpty() && arr[dq.peekLast()] >= arr[i]) {
                dq.pollLast();
            }

            dq.offerLast(i);

            bw.write(arr[dq.peekFirst()]+" ");
        }

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

---

4. 결과 및 회고

출력할 때 리스트를 사용했었는데 시간초과가 났었다. 이 문제는 O(N) 이하 시간 복잡도를 가질 수 있냐가 핵심인 것 같다.