스택 - 오큰수

🔎 문제

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

🔍 문제 분석

(1) 스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수는 오큰수

(2) 오큰수를 구한 후 수열에서 오큰수가 존재하지 않는 숫자에 -1 출력

(과정-1) 스택이 채워져 있고 A[index] > A[top]인 경우 pop한 인덱스를 이용하여 정답 수열에 오큰수를 저장, pop은 조건을 만족하는 동안 계속 반복
(과정-2) 현재 인덱스를 스택에 push하고 다음 인덱스로 넘어감
(과정-3) 과정 1~2를 수열 길이만큼 반복한 다음 현재 스택에 남아있는 인덱스에 -1 저장

👀 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class BackJoon_17298 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    
        int N = Integer.parseInt(bf.readLine());
        int[] A = new int[N]; 
        int[] ans = new int[N]; // 정답배열
        String[] str = bf.readLine().split(" ");
        for(int i = 0; i < A.length; i++) {
            A[i] = Integer.parseInt(str[i]);
        }

        Stack<Integer> stack = new Stack<>();
        stack.push(0); //초기 값은 항상 비어있으므로 0을 push해 초기화
        for(int i = 1; i < N; i++) {
            // 스택이 비어있지 않거나, 현재 스택이 push할 값보다 작을 경우
            while (!stack.isEmpty() && A[stack.peek()] < A[i]) {
                ans[stack.pop()] = A[i]; // 정답 배열에 오큰수 저장
            }
            stack.push(i);
        }
        while(!stack.empty()) {
            ans[stack.pop()] = -1;
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i = 0; i < N; i++) {
            bw.write(ans[i] + " ");
        }
        bw.write("\n");
        bw.flush();
    }
}