[백준 17298] 오큰수 (JAVA)

문제

https://www.acmicpc.net/problem/17298

풀이

스택을 이용해서 풀면 됩니다.

1) 스택이 비어있으면 무조건 push
2) 지금 숫자가 peek한 숫자보다 크면 pop후 index 확인 후 지금 숫자를 입력
3) 2)번을 반복하다 peek한 숫자가 더 크면 push
4) 모두 처리했으면 스택에 남은 숫자들 전부 -1 넣기

예시)
넣을 숫자 3 5 2 7

1) 숫자 : 3
stack[] => 비어있으므로 push
arr[][][][]

2) 숫자 : 5
stack[(3,0)] => 5보다 작으므로 pop
arr[5][][][] => 5 저장
stack[] => 비어있으므로 push

3) 숫자 : 2
stack[(5,1)] => 2가 작으므로 push
arr[5][][][]

4) 숫자 7
stack[(5,1), (2,2)] => 7보다 작으므로 pop
arr[5][][7][] => 7 저장
stack[(5,1)] => 7보다 작으므로 pop
arr[5][7][7][] => 7 저장
stack[] => 비어있으므로 push

5) 나머지 -1 처리
stack[(7,3)] => -1 처리
arr[5][7][7][-1]

코드

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        Stack stack = new Stack(N);
        int[] ans = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());

            while (!stack.isEmpty() && stack.peek().num < num) {
                Node node = stack.pop();
                ans[node.idx] = num;
            }

            stack.push(new Node(num, i));
        }

        while (!stack.isEmpty()) {
            Node node = stack.pop();
            ans[node.idx] = -1;
        }

        for (int i : ans) {
            sb.append(i).append(' ');
        }

        System.out.println(sb);
        br.close();
    }

    public static class Stack {
        Node[] stack;
        int idx = 0;

        public Stack(int N) {
            stack = new Node[N];
        }

        public void push(Node node) {
            stack[idx++] = node;
        }

        public Node peek() {
            return stack[idx-1];
        }

        public Node pop() {
            return stack[--idx];
        }

        public boolean isEmpty() {
            return idx == 0;
        }
    }

    public static class Node {
        int num, idx;

        public Node(int num, int idx) {
            this.num = num;
            this.idx = idx;
        }
    }
}