Java 문제풀이 - 최솟값 찾기

문제

N개의 수 A1, A2, ..., AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 Ai가 주어진다. (-10^9 ≤ Ai ≤ 10^9)

출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

나의 풀이

import java.io.*;
import java.util.StringTokenizer;
import java.util.Deque;
import java.util.ArrayDeque;
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        Deque<Node> inputDeque = new ArrayDeque<>();

        st = new StringTokenizer(bf.readLine());
        // 문제 조건이 A1부터 시작하므로 1부터 시작
        for (int i = 1; i < N + 1; i++) {
            int firstIndexRange = (i - L + 1) > 0 ? i - L + 1 : 1;
            Node inputNode = new Node(i, Long.parseLong(st.nextToken()));
            // 덱이 비어 있을 경우 그냥 삽입
            if (inputDeque.isEmpty()) {
                inputDeque.addLast(inputNode);
            } else {
                // 새로 넣기 전에 덱의 뒤쪽의 Value 체크
                while (true) {
                    // 덱이 비어 있으면 바로 삽입
                    if (inputDeque.isEmpty()) {
                        inputDeque.addLast(inputNode);
                        break;
                    } else {
                        Node lastNode = inputDeque.peekLast();
                        if (lastNode.value >= inputNode.value) {
                            inputDeque.removeLast();
                        } else {
                            inputDeque.addLast(inputNode);
                            break;
                        }
                    }
                }

                // 비어 있지 않으면 우선 맨 앞의 Index 범위 체크
                Node firstNode = inputDeque.getFirst();
                if (firstNode.index < firstIndexRange) {
                    inputDeque.removeFirst();
                }
            }
            bw.write(inputDeque.getFirst().value + " ");
        }
        bw.flush();
        bw.close();
    }
    static class Node {
        public int index;
        public long value;

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

예시 풀이

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

public class P11003_최솟값찾기 {
  public static final Scanner scanner = new Scanner(System.in);

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    // 출력을 그때 그때 하는 것보다 버퍼에 넣고 한번에 출력하기 위해 BufferedWriter를 사용
    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());
      // 새로운 값이 들어 올 때마다 정렬하지 않고 현재 수보다 큰 값을 덱에서 제거함으로써 시간복잡도를 줄일 수 있음
      while (!mydeque.isEmpty() && mydeque.getLast().value > now) {
        mydeque.removeLast();
      }
      mydeque.addLast(new Node(now, i));
      // 범위에서 벗어난 값은 덱에서 제거
      if (mydeque.getFirst().index <= i - L) {
        mydeque.removeFirst();
      }
      bw.write(mydeque.getFirst().value + " ");
    }
    bw.flush();
    bw.close();
  }

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

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

리뷰

슬라이딩 윈도우를 데크로 구현하는 문제였다. 데크라는 자료구조를 한 번도 접한 적이 없어서 많이 헤맸다.

System.out.println을 사용하면 시간 초과가 뜨고, BufferedWriter를 사용해야 정답으로 출력되는 문제였다. 앞으로 시간 초과가 떴을 때 위를 염두해야겠다.