[백준 17298번] 오큰수

문제 링크: 17298번 오큰수

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

 

프로그래머스 레벨 2였나... 주식 가격 문제와 비슷하다.

수열의 원소들을 쭉 받아주면서, 해당 숫자의 인덱스와 함께 묶어 스택에 push한다.

그리고 스택의 top에 있는 숫자보다 새로 받은 숫자가 더 크면, 더 작은 숫자가 나올때까지 스택을 pop해나가면서 각 인덱스에 새로 받은 숫자를 채워준다.

이런 과정을 반복했을 때 남은 숫자는 자신보다 더 큰 숫자를 만나지 못한 숫자들이므로, 스택에 남아있는 모든 아이템을 확인하면서 해당 인덱스의 자리에 -1을 채워준다.

 

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

public class Main {
    static class NumAndIdx {
        int num;
        int idx;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int[] answer = new int[n];

        Stack<NumAndIdx> stack = new Stack<>();

        st = new StringTokenizer(br.readLine());
        for (int idx = 0; idx < n; idx++) {
            int cur = Integer.parseInt(st.nextToken());

            while (!stack.isEmpty() && cur > stack.peek().num) {
                NumAndIdx top = stack.pop();
                answer[top.idx] = cur;
            }

            stack.push(new NumAndIdx(cur, idx));
        }

        while (!stack.empty())
            answer[stack.pop().idx] = -1;

        StringBuilder sb = new StringBuilder();
        for (int item : answer)
            sb.append(item).append(' ');
        System.out.print(sb);
    }
}