BOJ_11003 : 최솟값 찾기

👉 문제링크

11003번: 최솟값 찾기

---

---

🔸 문제 분석 🔸

• 일정 범위 안에서 최소값을 구하는 문제이므로 슬라이딩 윈도우와 정렬을 사용해야 한다.
  • 윈도우의 크기는 최소값을 구하는 범위가 i-L+1 ~ i 이므로 L로 생각한다.
  • 일반적으로 정렬은 O(nlogn)인데 N,L 의 범위가 5,000,000까지 이므로 정렬은 사용하지 못한다.
  • O(n)의 시간 복잡도로 해결해야되므로 윈도우를 덱(deque)로 구현하여 정렬 효과를 낸다.
• 덱은 (인덱스, 숫자) 형태의 노드를 클래스로 구현하여 저장한다.
• 새 노드를 오른쪽으로 삽입
  • 마지막 노드의 값이 새 노드보다 크면 삭제하고, 새 노드 삽입
  • 마지막 노드의 값이 새 노드보다 작으면, 새 노드 그냥 삽입
• 윈도우의 크기보다 덱의 원소들의 인덱스 범위가 커지면, 맨 앞 노드 삭제
• 최소값 출력(배열 끝까지 반복)

🔸 코드 🔸

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

public 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());
        st = new StringTokenizer(br.readLine());
        Deque<Node> deque = new LinkedList<>();
        for (int i = 0; i < n; i++){
            int now = Integer.parseInt(st.nextToken());
            // 새로운 값이 들어올 때마다 정렬 대신 현재 수보다 큰 값을 덱에서 제거

            while (!deque.isEmpty() && deque.getLast().value > now){
                deque.removeLast();
            }
            deque.addLast(new Node(now, i));
            // 범위에서 벗어난 값은 덱에서 제거
            if (deque.getFirst().index <= i-l){
                deque.removeFirst();
            }
            bw.write(deque.getFirst().value + " ");
        }
        bw.close();
    }

    static class Node{
        public int value;
        public int index;

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

🔸 코드 해석 🔸

• Node클래스를 만들어 값과 인덱스를 저장한다.
• 덱 을 Node 클래스를 사용해서 선언한다.
• 수를 하나씩 입력받으며 계산을 반복한다. 
  • 새로운 값이 들어올 때마다 마지막 값이 새 값보다 크다면, 반복해서 제거하고 새 값을 넣는다.
  • 만약 맨 앞 값의 인덱스가 범위를 벗어나면, 윈도우가 l보다 커진 것이므로 맨 앞 값을 제거한다.
  • 현재 가장 앞에 있는 수가 범위의 최소값이므로 출력한다.

 

---

🔸 end 🔸

• 처음 풀어본 골드1 문제였는데, 교재의 풀이가 없었다면 풀 수 없었을 것 같다.
• java에서 덱 등의 기본적인 자료구조를 많이 연습할 필요성을 느꼈다.
• 태그의 우선순위 큐가 있는 걸 보니, 덱 대신 우선순위 큐를 사용해 정렬을 대신할 수 있어 보인다.