[17298] 오큰수 (JAVA)

# 문제 설명

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

---

입력

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

---

출력

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

 

# 정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken()); //수열 A의 크기
        int[] A = new int[N]; //수열 배열
        int[] output = new int[N]; //정답 배열

        st = new StringTokenizer(br.readLine());
        for (int n = 0; n < N; n++) {
            A[n] = Integer.parseInt(st.nextToken());
        }

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

        for (int n = 1; n < N; n++) {
            while (!stack.isEmpty() && A[stack.peek()] < A[n]) {
                output[stack.pop()] = A[n];
            }
            stack.push(n);
        }

        while (!stack.isEmpty()) {
            output[stack.pop()] = -1;
        }

        for (int o : output) {
            sb.append(o + " ");
        }

        System.out.print(sb);
    }
}

 

수열 배열 A와 정답을 저장할 output을 생성한다.

반복문을 사용하여 A에 값들을 넣어준다.

 

stack을 만들고 첫번째 인덱스인 0을 넣는다.

그 다음 1부터 N-1까지 반복하며 오큰수를 찾아 output에 저장한다.

stack이 비어있지 않고 A에서 stack의 가장 위의 인덱스가 가리키는 값이 A[n]보다 작으면, A[n]이 해당 인덱스의 오큰수이다. 따라서 output[stack.pop()]에 A[n]을 저장한다.

이를 반복하여 오큰수를 모두 찾는다.

 

stack에 남아있는 인덱스들은 오큰수가 없는 수이므로 output에 -1을 넣어줘야 한다.

stack이 빌 때까지 pop하여 -1을 넣는다.

 

output에 있는 값들을 StringBuilder에 추가하여 출력한다.