[스택] 백준 17298번 오큰수(Java)

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

17298번: 오큰수

📚 문제

Ai의 오큰수 NGE(i)는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다.

A = [9, 5, 4, 8]인 경우 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE($) = -1이다.

 

📝 문제 해결

입력받은 수들을 먼저 배열에 넣어주고 0번 인덱스부터 차례대로 값을 stack에 넣어준다.

stack이 비어있지 않으면서 새로 들어올 값이 해당 인덱스(stack 맨 위의 값)의 배열 값보다 크다면

stack의 맨 위 값을 pop하고 해당 인덱스의 배열값을 새로운 값으로 교체해준다.

	input	stack
처음이라 스택이 비어있으므로 push 0	{3, 5, 2, 7}	{0}
스택이 비어있지 않고 input[0] < input[1]이므로 pop 0 그리고 input[0] = input[1]	{5, 5, 2, 7}	{}
push 1	{5, 5, 2, 7}	{1}
스택이 비어있지 않으나 input[1] > input[2]이므로 input 변화 없음	{5, 5, 2, 7}	{1}
push 2	{5, 5, 2, 7}	{1, 2}
스택이 비어있지 않고 input[2] < input[3] 이므로 pop 2 그리고 input[2] = input[3]	{5, 5, 7, 7}	{1}
스택이 비어있지 않고 input[1] < input[3] 이므로 pop 1 그리고 input[1] = input[3]	{5, 7, 7, 7}	{}
push 3	{5, 7, 7, 7}	{3}
스택이 비어있지 않으므로 pop 3 그리고 input[3] = -1	{5, 7, 7, -1}	{}

 

💻 코드

package algorithm;

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

public class BOJ17298 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Integer> stack = new Stack<Integer>();

        int N = Integer.parseInt(br.readLine());
        int[] input = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 0; i < N; i++) {
            while(!stack.isEmpty() && input[stack.peek()] < input[i]) {
                input[stack.pop()] = input[i];
            }

            stack.push(i);
        }

        while(!stack.isEmpty()) {
            input[stack.pop()] = -1;
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < N; i++) {
            sb.append(input[i]).append(' ');
        }

        System.out.println(sb);
    }
}