[Java11] 백준 17298번 : 오큰수

백준 17298번 : 오큰수

수열A의 원소 A_n에 대하여, m > n 이고 A_n < A_m을 만족하는 가장 작은 m (A_m = 오큰수)을 찾는 문제이다.

입력된 값은 이전 입력값보다 클 수도 있고 작을 수도있다.
입력된 값이 이전값 보다 작으면 이후에 입력될 다른 값중 하나가 오큰수가 될 수도 있고 없을 수도 있다.
만약 입력된 값이 이전값 보다 크다면 해당 값의 오큰수는 입력값이 될 것이고, 그보다 더 전에 입력된 값과 또 비교를 하여 오큰수인지 판단하여야한다.
그리고 한번 오큰수는 최소인 m에 해당하는 값이므로 한번 결정되면 더이상 변하지 않는다.
이러한 특징은 스택을 사용하여 입력값이 이전보다 작으면 push하여 기다리다가 이전값보다 큰 경우에는 pop을 함으로써 구현할 수 있다.

값이 입력되면 먼저 직전 값과 비교를 하여 입력값이 더 크다면 입력값보다 더 큰 값을 만날때 까지 계속 pop한다. 그 후 입력값을 push한다. 모든 반복이 종료되었음에도 스택에 남이있는 경우는 오큰수가 없는 경우이다.

그래서 -1로 초기화된 배열을 만들고, Node에 index라는 필드를 추가하여 pop된 각 Node의 index에 해당하는 배열의 위치에 오큰수를 저장할 수 있게 하였다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Baekjoon_17298 {
  static class Stack {
    static class Node {
      private final int data;
      private Node next;
      private final int index;

      public Node(int data, int index) {
        this.data = data;
        this.next = null;
        this.index = index;
      }
    }

    private Node head;
    private int size;

    public Stack() {
      head = null;
      this.size = 0;
    }

    public void push(int data, int index) {
      Node newNode = new Node(data, index);
      newNode.next = head;
      head = newNode;
      size++;
    }

    public void pop() {
      if (head == null) return;
      head = head.next;
      size--;
    }

    public boolean empty() {
      return size == 0;
    }

    public Node top() {
      return head;
    }
  }

  public void result() throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력받기
    StringBuilder sb = new StringBuilder();

    Stack stack = new Stack();

    int n = Integer.parseInt(br.readLine());
    int[] arr = new int[n];
    Arrays.fill(arr, -1);

    String str = br.readLine(); // 한줄씩 받기
    StringTokenizer st = new StringTokenizer(str); // " "를 기준으로 나눈기

    for (int i = 0; i < n; i++) {
      int input = Integer.parseInt(st.nextToken());
      while (!stack.empty() && stack.top().data < input) {
        arr[stack.top().index] = input;
        stack.pop();
      }
      stack.push(input, i);
    }

    for (int i = 0; i < n; i++) {
      sb.append(arr[i]).append(" ");
    }

    System.out.println(sb);
  }

  public static void main(String[] args) throws Exception {
    new Baekjoon_17298().result();
  }
}