백준 문제 풀이 (44) 11003 : 최솟값 찾기

 

 

음.. 난이도는 골드 1인데 푸는 방법만 알면 어지간한 실버 문제보다 쉽다.

찾아보니 원래 플레티넘 문제였는데 골드로 강등당했네..

 

연속된 수가 같은 범위로 이동하기 때문에 윈도우 슬라이딩 알고리즘을 이용할 것이다.

뭔지 모르면 밑에 문제 먼저 풀어보자.

사실 간단해서 몰라도 금방 배울 수 있다.

 

https://7357.tistory.com/240?category=1066252 

백준 java 문제풀이 (43) 12891 : DNA 비밀번호

 

 

 

 

우선 문제에서 제공하는 정보를 먼저 확인해보자.

 

첫 번째로 N개의 수가 주어지며, 우리가 구해야하는 D(i)는 수는 A(i-L+1) ~ A(i)중의 최소 값을 의미한다.

끄덕끄덕..

그다지 어렵지 않은 설명인데, 난 처음 보고 이게 뭔 소린가 싶었다.

 

 

머리가 나쁘면 몸이 고생해야하는 법이다. 직접 그려서 확인해보자.

 

 

 

끄덕끄덕.. 이제 초등학생도 알 수 있게 되었다.

영락없는 슬라이딩 윈도우 알고리즘 문제다.

 

그냥 일정 범위를 유지하며 움직이면서 한 쪽으로는 넣어주고, 한 쪽으로는 뱉어주면 될 것 같다.

어디서 많이 들어본 말이다.

 

FIFO.. 바로 Queue다.

그런데 이 문제는 Queue로는 해결되지 않는 문제가 있다.

우리에게 필요한 것은 오직 최소값이기 때문에 

만약 슬라이더 안에 숫자가 1 5가 들어있고 새로 들어오는 숫자가 2라면 5는 아무 필요가 없다.

그러면 앞으로도 뱉고 뒤로도 뱉는 자료구조면 좋겠다.

 

그거 완전 LinkedList네.

근데 난 LinkedList를 안 좋아한다. 느리잖아요.

 

ArrayDeque는 어떨까요.

 

근데 여러분은 Deque가 디큐가 아닌 덱이라는 사실.. 알고 있었나요. 전 오늘 처음 알았습니다..

 

 

 

 

 

 

 

엔큐 디큐하면서 넣고 빼는게 귀엽다.

 

아무튼 이제 위에서 얘기한대로 넣고 빼고 하면 끝이다.

 

for () {

1. 차례로 넣으면서 만약 새로 들어오는 값이 뒤에서 대기 중인 값보다 크다면 ? 날려버리자

2. 최소값은 항상 1번 인덱스에 있도록 할 예정이니 1번 반복마다 얘를 StringBuilder에 넣던지 어쩌던지.. 하시면 되겠네요

3. 만약 최소값의 인덱스가 i-L+1이 된다면 날려주ㅏ

}

 

이거 쓰고 보니까 생각났네.

인덱스가 문제다.

 

나 같은 경우는 클래스를 만들어서 풀었다.

그런데 그렇게 번거로운 방법을 사용할 필요 없이, 덱에는 인덱스 위치만 저장하고 문제에서 제공해주는 어레이랑 1:1로 인덱스를 대응시켜서 푸는 것도 방법이다.

 

개인적으로 실수할 여지가 줄어드는 클래스 쪽이 낫다고 생각한다.

정답은 아래에

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        // 첫 번째 줄 숫자 개수 N, 임의 값 L
        // 두 번째 줄 N개의 수 배열
 
        //  i-L+1 => A(i-l+1) ~ Ai
        // 입력값 처리 시작
        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[] arr = new int[N];
 
        st = new StringTokenizer(br.readLine(), " ");
        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        // 입력값 처리 끝
        // 덱 생성
        Deque<Node> deque = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
 
        for (int i=0; i<arr.length; i++) {
            Node node = new Node(i, arr[i]);
            int min = i-L+1;
 
            while (deque.size() != 0 && !node.compareToNode(deque.getLast())) {
                deque.removeLast();
            }
 
            deque.add(node);
 
            sb.append(deque.getFirst().getValue()).append(" ");
 
            if (deque.getFirst().getIndex() == min) {
                deque.removeFirst();
            }
        }
 
        System.out.println(sb);
    }
}
 
class Node {
    private final int index;
    private final int value;
 
    public Node (int index, int value) {
        this.index = index;
        this.value = value;
    }
 
    public boolean compareToNode(Node node) {
        return this.value > node.getValue();
    }
 
    public int getValue() {
        return this.value;
    }
 
    public int getIndex() {
        return this.index;
    }
}