🐣 백준 Q11003 - 최소값 찾기 (java)

문제

---

• 백준 Q11003 - 최소값 찾기

슈도 코드

---

	N(데이터 개수) L(최솟값을 구하는 범위)
	Deque<Node> mydeque(데이터를 담을 덱 자료구조)
	for(N만큼 반복)
	{
		now(현재 데이터 값)
		 덱의 마지막 위치에서부터 now보다 큰 값은 덱에서 제거하기
		 덱의 마지막 위치에 now값 저장하기
		 덱의 1번째 위치에서부터 L의 범위를 벗어난 값(now index-L <= index)을 덱에서 제거하기
		 덱의 1번째 데이터 출력하기
	}
	덱에 저장할 노드 클래스 별도 생성하기
	노드 클래스에는 index(자신의 위치), value(자신의 값) 담

덱(Deque) 연산
왼쪽에서 함수가 삽입, 삭제 : addFirst(), removeFirst()
오른쪽에서 함수가 삽입, 삭제 : addLast(), removeLast()

코드

---

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

public class Q11003_최소값찾기 {
  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());

    st = new StringTokenizer(br.readLine());
    Deque<Node> myDeque = new LinkedList<>();
    for(int i = 0 ; i < N; i++) {
      int now = Integer.parseInt(st.nextToken());
      // 1️⃣ (0,1)
      // 2️⃣ (1,5)
      // 3️⃣ (2,2)
      // 4️⃣ (3,3)
      // 5️⃣ (4,6)
      // ...

      // 새로들어올 값보다 더 큰 값이 있다면 제거 -> 오름차순으로 정렬되게 됨
      while(!myDeque.isEmpty() && myDeque.getLast().value > now) {
        myDeque.removeLast();
      }
      // -> 3️⃣(1,5) > (2,2)   ->    (1,5) 제거   ->(0,1), (2,2)

      myDeque.addLast(new Node(i, now)); // 새로운 값을 뒤에 추가해줌
      // -> 1️⃣(0,1)
      // -> 2️⃣(0,1), (1,5)
      // -> 4️⃣(0,1), (2,2), (3,3)
      // -> 5️⃣(0,1), (2,2), (3,3), (4,6)

      // 필요없는 앞부분의 숫자들 없애기
      if(myDeque.getFirst().index <= i - L) { // 첫번째 인덱스가 L의 범위를 벗어났다면 제거
        myDeque.removeFirst(); // 맨 앞에 있는 노드 삭제
      }
      // -> 5️⃣ 덱의 첫번째 인덱스(0) <= 4-L(3)    ->    (0,1) 제거

      bw.write(myDeque.getFirst().value + " "); // 오름차순으로 정렬되었기 때문에 맨 앞에 있는 것이 최소값
    }
    bw.flush();
    bw.close();
  }
  
  static class Node {
    public int index;
    public int value;

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

/*
---- 예제 입력 1 -----
12 3
1 5 2 3 6 2 3 7 3 5 2 6
----- 예제 출력 1 -----
1 1 1 2 2 2 2 2 3 3 2 2
 */