[백준/JAVA] 17298번 오큰수

• 스택으로 풀 수 있는 꽤 어려운 문제
  https://www.acmicpc.net/problem/17298

1. 문제

크기가 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이다.

2. 문제 접근

1) 첫째 줄에 수열 A의 크기 N을 입력받는다.
2) N의 크기만큼 스택 배열 하나와 출력을 할 배열 하나를 선언하고 출력을 할 배열은 모두 -1로 초기화한다.
3) N만큼 반복하면서 수열 A의 원소를 입력받는다.
4) 원소를 입력받을 때 스택에 있는 수를 하나씩 꺼내 비교하면서 입력받은 수가 스택에서 꺼낸 수보다 클경우 출력 배열에 스택에서 꺼낸 원소의 인덱스에 입력받은 수를 저장한다.
5) 입력받은 수가 더이상 크지 않을 때까지 반복한 후에 스택에 입력받은 원소를 저장한다.
6) N 반복이 끝난 후 출력 배열의 수들을 출력한다.

3. 코드

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int stack[] = new int[N];
        int result[] = new int[N];
        StringBuilder sb = new StringBuilder();
        for(int i =0;i<N;i++) {
            result[i] = -1;
        }
        int top = -1;
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=0;i<N;i++) {
            int input = Integer.parseInt(st.nextToken());
            int t= i-1;
            while(top>=0 && stack[top] < input) {
                if(result[t]==-1) {
                    result[t]= input;
                    top--;
                    t--;
                }
                else {
                    t--;
                }
            }
            stack[++top] = input;
        }
        for(int i=0;i<N;i++) {
            sb.append(result[i]).append(" ");
        }
        System.out.println(sb);
    }
}