[백준_JAVA_알고리즘] 17298 오큰수 #스택

 

가장 최근에 확인한 수부터 처리하기 위해, 스택의 LIFO를 이용합니다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        Stack<Integer> stack = new Stack<>();

        int A = Integer.parseInt(bufferedReader.readLine());
        int[] arr = new int[A]; // 입력 수열
        int[] result = new int[A]; // 오큰수 저장 배열

        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        for(int a = 0; a < A; a++){
            arr[a] = Integer.parseInt(stringTokenizer.nextToken());
        }

        for(int i = 0; i < result.length; i++){
            result[i] = -1; // -1로 초기화
        }

        stack.push(0);

        for(int j = 1; j < arr.length; j++){
            while(!stack.isEmpty() && arr[stack.peek()] < arr[j]){
                result[stack.pop()] = arr[j];
            }
            stack.push(j);
        }

        for (int k : result) {
            stringBuilder.append(k).append(" ");
        }
        System.out.println(stringBuilder);
    }

}

 

arr 배열에는 입력받은 수열을 저장하고, result 배열은 오큰수를 저장합니다.

먼저 스택에 첫 번째 수의 인덱스(0)를 넣습니다. 그리고 두 번째 수부터 순회하면서, 현재 수가 스택의 top이 가리키는 수보다 크다면, 현재 수가 스택 top의 오큰수가 됩니다.

 

.

.

.

 

문제는 아래에서 확인할 수 있습니다.
https://www.acmicpc.net/problem/17298