백준 17298 오큰수 Java

단계별로 풀어보기 -> 스택에 있는 오큰수 문제이다.

 

오큰수는 말 그대로 오른쪽에서 가장 첫 번째로 큰 수이다.

1번부터 N번까지의 오큰수를 출력하면 되는 문제이다.

 

N의 최대 크기는 백만이니까 당연히 O(N^2)으로 탐색하는 방법은 안된다.

스택을 사용해야 한다는 걸 알고 문제를 접했기 때문에

스택으로 어떻게 O(N)만에 처리할지 고민해야 한다.

 

내가 푼 방식은

N개의 값들을 N크기의 배열에 넣고

for문을 n-1부터 0까지 돌린다.

1. 스택의 top부분보다 배열[i]가 크다면 배열[i]가 더 작을 때까지 pop 해준다.

2. 스택이 비어있다면 배열[i]보다 더 큰 수가 없는 것 = 오큰수가 없는 것,  i번째 오큰수는 -1

3. 스택의 top이 배열[i]보다 크다면 i번째 오큰수는 스택의 top

4. 스택에 배열[i] 삽입

 

이 방식이 가능한 이유는

오큰수는 i번째 수의 오른쪽에서 첫 번째로 만난 i번째 수보다 큰 수이기 때문에

스택에서 배열[i]보다 작은 수들을 전부 지워줘도 지워진 수들이 오큰수가 될 확률이 없기 때문이다.

 

쉬워 보였지만 굉장히 헷갈렸던 문제였다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Q17298 {
    public static void main(String[] args) throws Exception{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        StringTokenizer st = new StringTokenizer(reader.readLine());
        int [] a = new int[n];
        for(int i=0; i<n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        Stack<Integer> s = new Stack<>();
        int [] ans = new int[n];
        StringBuilder sb = new StringBuilder();
        for(int i=n-1; i>=0; i--) {
            while(!s.isEmpty() && s.peek() <= a[i]) {
                s.pop();
            }
            if(s.isEmpty()) {
                ans[i] = -1;
            } else {
                ans[i] = s.peek();
            }
            s.push(a[i]);
        }
        for(int k : ans) {
            sb.append(k+" ");
        }
        System.out.print(sb.toString());
    }
}