[백준] 오큰수

• 문제 링크 : https://www.acmicpc.net/problem/17298

• 문제 해결 :
  크기가 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이다.
  
  이 문제는 스택으로 구현하였는데, 스택에는 현재 오큰수를 찾지 못한 숫자의
  배열 인덱스값이 들어가도록 하였다.
  숫자를 차례대로 넣으면서, 만약 현재 스택의 peek에 있는 인덱스의 숫자가 현재 숫자보다 작다면, 오큰수를 찾은 것이므로 pop하였고, 이렇게 한다면 스택 내부의 인덱스의 숫자들은 내림차순으로 될것이기 때문에, 현재 숫자가 오큰수가 될 가능성이 있으므로 계속 검사하는 방식으로 하였다.
  마지막으로 끝까지 이 과정을 반복했을 때 스택에 숫자가 남아있다면, 스택에는 현재
  오큰수를 찾지 못한 수가 들어있으므로
  또한 오큰수를 구했다면 배열에서 오큰수를 바로 초기화 해주어 바로 출력할 수 있도록 하였다.
  
  예를 들면, [3,5,2,7]에서 오큰수를 만든다고 했을 때

1. [3,5,2,7] / 스택(인덱스) []
2. [3,5,2,7] / 스택(인덱스) [0]
3. [3,5,2,7] -> [5,5,2,7] / 스택(인덱스) [0,1] -> [1] pop
4. [5,5,2,7] / 스택(인덱스) [1,2]
5. [5,5,2,7] -> [5,7,7,7] / 스택(인덱스) [1,2,3] -> [1,3] pop -> [3] pop
6. 끝까지 진행하였지만 스택에 인덱스 숫자가 남아있는 것은 -1로 초기화
   [5,7,7,7] -> [5,7,7,-1]

public class Q17298 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();

        int[] arr = new int[N];

        String[] input = br.readLine().split(" ");

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.valueOf(input[i]);
        }

        for (int i = 0; i < N; i++) {


            if (!stack.empty() && arr[stack.peek()] < arr[i]) {
            /*스택이 비어있지않고 스택의 peek값을 인덱스로 같는 배열의 값보다 현재 숫자가 크다면 
            스택에서 꺼내고 배열의 값을 오큰수로 변경*/
                while (!stack.empty() && arr[stack.peek()] < arr[i]) {
                    arr[stack.pop()] = arr[i];
                }
            }

            stack.push(i);


        }

        if (!stack.empty()) {
            while (!stack.empty()) {
                arr[stack.pop()] = -1;
            }
        }

        for (int i : arr) {
            sb.append(i + " ");
        }

        System.out.println(sb);

    }
}