[Java] 11003번. 최솟값 찾기

1. 문제 분석

N개의 크기를 가진 정수 배열에서, L크기의 범위 안에서의 최솟값을 찾는 문제이다.

이렇게 말하면 이해가 어렵기 때문에 바로 예제를 보자.

 

예제)

크기(N)가 12인 정수 배열 [1, 5, 2, 3, 6, 2, 3, 7, 3, 5, 2, 6]일 때,

범위(L)가 3인 배열에서의 최솟값이다.

 

인덱스가 0~2 인 값들의 최솟값,

인덱스가 1~3 인 값들의 최솟값,

인덱스가 2~4 인 값들의 최솟값,

...

인덱스가 10~12 인 값들의 최솟값

을 배열로 구하면 된다.

 

이는 크기가 3인 배열을 이용해서 구할 수 있다.

 

위의 그림은 배열 [1, 5, 2, 3, 6, 2, 3, 7, 3, 5, 2, 6]에 대한 예제이다.

가장 먼저 들어온 값은 가장 먼저 나간다.

 

❗ 중요 ❗

여기서 배열에 들어온 수 들을 살고 죽는 문제로 따져보면, 각자 살 수 있는 시간은 3타임이다.

 

(MBTI의 N적 사고로 생각해보아요ㅎㅎ)

모든 사람은 수명이 같고 타고난 재능을 이길 수 없는 세상이며 가장 뛰어난 사람만 알아봐준다고 가정하자.

'나'를 이미 들어가 있는 요소라고 생각하고 상상해보자.

 

만약, 나보다 살 날이 많고 뛰어난 사람이 들어온다면 나는 죽을 때 까지 이길 수 없다.

좀 잔인한 얘기이긴 하지만 배열 세계에서 내가 존재할 이유가 없어진다.

 

또 다른 예시로, 내가 만약 가장 뛰어난 사람이었고 뒤에 나보다 뛰어나지 않은 사람이 들어온다면

뒤에 들어온 사람은 나보다 수명이 길기 때문에 내가 죽은 후 가장 뛰어난 사람이 될 수도 있다.

 

즉, 요소가 사라지는 경우는 두가지이다.

(1) 수명이 끝난 경우

(2) 이후에 나보다 뛰어난 요소가 들어온 경우

 

이 비유를 문제에 적용해보면 다음 그림과 같아진다.

여기서 핑크 배경은 각 타이밍에서의 최솟값이고

빨간색 글씨는 최솟값이 새로들어와 사라진 요소이다. 실제로는 없다고 생각하면 된다.

 

그렇게 보면 각 최솟값은 각 타이밍에서 가장 아래에 위치하게 된다는 점을 알 수 있다.

 

2. 구현

사용할 주요 변수

deque : L크기를 가진 배열. 이 때 배열에 들어갈 요소는 index와 value 값을 가지고 있는 int 배열이다.

 

해결 과정

(1) Deque에 모든 요소가 한번씩 들어갈 때 까지 아래 과정을 반복한다.

(2) 첫 요소는 비교 대상이 없으므로 index값과 value를 함께 추가한다.

(3) index값이 끝난 요소는 삭제한다.

(4) 요소를 추가 할 때, 추가될 요소의 value보다 큰 값들은 모두 삭제하고 새 요소를 추가한다.

(5) 최종 출력할 결과값에 현재 Deque의 가장 앞에 있는 요소의 valule값을 추가한다.

 

3. 최종코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

class Main {
    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());

        int n = Integer.parseInt(st.nextToken());
        int l = Integer.parseInt(st.nextToken());

        Deque<int[]> deque = new ArrayDeque<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());

            while (!deque.isEmpty() && deque.peekLast()[0] > num) {
                deque.pollLast();
            }

            deque.addLast(new int[]{num, i});

            if (deque.peekFirst()[1] <= i - l) {
                deque.pollFirst();
            }

            bw.write(Integer.toString(deque.peekFirst()[0])+" ");
        }
        br.close();
        bw.close();
    }
}