[Java][백준 17298: 오큰수]

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

17298번: 오큰수

Problem 

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

 

Input

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

 

Output

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

Insight 

1. 자신의 오른쪽에 위치하는 수 중 가장 가까이 있으면서 자신보다 큰 수를 찾아야 한다. 

2. 오른쪽에 있는 수 중 자신보다 큰 수가 하나 있다면 그 뒤로 부터는 어떤 수가 오는지는 상관이 없다. 

3. 숫자배열을 뒤에서 부터 확인하여 자신보다 큰 수가 있으면 pop, 없으면 push 

<Process> 
input:
4
3 5 2 7

1. 숫자배열을 7->2->5->3 순서로 확인
2. 7은 오른쪽에 숫자가 없기 때문에 7의 오큰수는 -1 저장 후 임시스택에 7 저장 
3. 2는 임시스택에 peek인 7보다 작기 때문에 2의 오큰수 7 저장 후 임시스택에 2 저장
3. 5는 임시스택에 peek인 2보다 크기 때문에 임시스택에서 2삭제 후 다시 임시스택에 peek인 7보다 작기 때문에 5의 오큰수 7 저장 후 임시스택에 5 저장
4. 3은 임시스택에 peek인 5보다 작기 때문에 3의 오큰수 5 저장 

 

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

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));
        
        Stack<Integer> stack = new Stack<>(); 
        Stack<Integer> stack2 = new Stack<>(); //임시스택 
        Stack<Integer> result = new Stack<>(); //결과 저장 할 스택 
        
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        for(int i=0; i<N; i++){
            stack.push(Integer.parseInt(st.nextToken())); 
        }
        
        for(int i=0; i<N ; i++){
            int k = stack.pop(); 
            while(!stack2.empty() && stack2.peek() <= k ){
                stack2.pop(); 
            }
            if (stack2.empty()){
                result.add(-1);
                stack2.push(k);  
            }
            else{
                result.add(stack2.peek());
                stack2.push(k); 
            }
        }
        while(!result.empty()){
            bw.write(String.valueOf(result.pop()));
            if(!result.empty()){bw.write(" ");}
        }
        
        bw.flush();
        bw.close(); 
    }
}