[백준] BOJ_17298 오큰수 JAVA

BOJ_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이다.

---

입력

첫째 줄에 수열 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.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Stack<Integer> st = new Stack<>();
        StringBuilder sb = new StringBuilder();

        int n = sc.nextInt();

        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        st.push(0);

        for (int i = 1; i < n; i++) {
            while (!st.isEmpty() && arr[st.peek()] < arr[i]) {
                arr[st.pop()] = arr[i];
            }

            st.push(i);
        }

        while(!st.isEmpty()){
            arr[st.pop()] = -1;
        }

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

        System.out.println(sb.toString());
    }
}

---

Comment

• 수열의 크기가 최대 1,000,000이다. 이중 for문으로 구현하면 시간초과 발생!
• 물론, 출력시에도 String.out.println()을 사용하지 않고 StringBuilder를 이용한 이유도 같은 이유(시간 초과)!
• 인덱스와 스택을 이용. 참고 항상 감사한 블로그다.

---