BOJ_17298_오큰수

걸린 시간: 50m

알고리즘 분류: Stack

가장 기본적인, 쉬운 스택 문제였지만 인덱스를 관리하는 아이디어를 떠올리지 못하여 시간이 오래 걸린 문제입니다. 조금 더 기본, 기초에 충실해야할 것 같습니다.

import java.io.*;
import java.util.*;

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());
        int[] nums = new int[N];
        int[] ans = new int[N];
        Arrays.fill(ans, -1); // 기본값을 -1로 설정

        StringTokenizer st = new StringTokenizer(br.readLine());
        Stack<Integer> stack = new Stack<>();

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

            // 스택의 top이 현재 숫자보다 작다면, pop하고 ans 배열 업데이트
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                ans[stack.pop()] = nums[i]; // pop한 인덱스의 오큰수를 현재 숫자로 설정
            }

            stack.push(i); // 인덱스를 저장
        }

        // 결과 출력
        for (int i = 0; i < N; i++) {
            sb.append(ans[i]).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}