21.03.22 - [BOJ] 17298. 오큰수

[suhyunsim]

문제

• 17298

핵심 아이디어

• 시간초과 조심
• Stack 활용해서 O(N)으로 풀이
• 스택에 인덱스를 넣는게 포인트

참고: 블로그

어려운 점, 실수

• 이중 for문으로 풀고 시간초과 남

풀이

package main.java.com.poogle.BOJ.Q17298;

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 Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] answer = new int[n];
        int[] arr = new int[n];
        Stack<Integer> stack = new Stack<>();

        String[] tmp = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(tmp[i]);
        }

        stack.push(0);
        for (int i = 1; i < n; i++) {
            if (stack.isEmpty()) {
                stack.push(i);
            }
            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                answer[stack.pop()] = arr[i];
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            answer[stack.pop()] = -1;
        }
        for (int i : answer) {
            bw.write(i + " ");
        }
        bw.write("\n");
        bw.flush();
    }

}