[JAVA/백준] 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이다.

<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)을 공백으로 구분해 출력한다.

 

<examples>
-입력

4
3 5 2 7

-출력

5 7 7 -1

 

 

[풀이]

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

public class P17298_오큰수 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int A[] = new int[N];
        int oken[] = new int[N];
        
        String str[] = br.readLine().split(" ");
        for (int i=0;i< N;i++){
            A[i] = Integer.parseInt(str[i]);
        }
        Stack<Integer> myStack = new Stack<>();
        myStack.push(0);//비어있는 스택에 0을 먼저 넣고 초기화
        for (int i=1;i<N;i++){ 
            while (!myStack.isEmpty() && A[myStack.peek()] < A[i]){
                oken[myStack.pop()] = A[i];
            }
            myStack.push(i); 
        }//N번 돌기 루프
        while (!myStack.empty()){//N번 돌고 나왔는데 스택이 비어있지 않다면
            oken[myStack.pop()] = -1;
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i=0;i<N;i++){
            bw.write(oken[i] + " ");
        }
        bw.write("\n");
        bw.flush();
    }
}

 

---

 

 

이 문제는 백준 골드4에 해당하는 문제로,

처음에는 for 반복문을 이용하여 비교 연산하고 결과로 담아내는 방법을 생각했으나

그렇게 하면 시간 복잡도 면에서 효율이 떨어지는 문제점이 생기는 것을 알았다.

이 문제는 LIFO의 특성을 가진 스택을 활용하여 시간 복잡도를 확 줄일 수 있는 문제이기 때문에

기존의 스택 개념을 잘 활용한다면 손 쉽게 해결이 가능하다.

 

조금 특이한 점은 stack에 index를 담아야 한다는 것이다.

오큰수라는 것 자체가 오른 쪽에 있는 큰 수를 이야기하는 것이니,

단순 값 비교가 아닌 인덱스를 스택에 push,pop 하며

결과 배열에 해당 인덱스에 오큰 수를 찾아 값을 집어넣는 것이다..