[백준] 17298_오큰수 - JAVA

백준_17298

17298번: 오큰수

 

스택

참고 포스팅

[백준] 1874_스택 수열 - JAVA

 

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        int[] A = new int[n]; // 수열 생성
        int[] answer = new int[n];  //정답 배열 생성
        String[] str = br.readLine().split(" ");

        for(int i = 0; i < n; i++) {
            A[i] = Integer.valueOf(str[i]);
        }

        Stack<Integer> myStack = new Stack<>();
        myStack.push(0);

        for(int i = 1; i < n; i++) {
            while(!myStack.isEmpty() && A[myStack.peek()] < A[i]) {
                answer[myStack.pop()] = A[i];
            }
            myStack.push(i);
        }
        while(!myStack.empty()) {

            answer[myStack.pop()] = -1;
    }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i = 0; i < n; i++) {
            bw.write(answer[i] + " ");
        }
        bw.write("\n");
        bw.flush();
    }
}

이 문제에서 핵심으로 생각할 포인트는 아래와 같다.

- 스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수는 오큰수가 된다.

- 오큰수를 구한 수열에서 오큰수가 존재하지 않는 숫자에 -1을 출력한다.

 

 

제출 결과