[JAVA] 자료구조 연습문제 - 백준 17298

입력 갯수와 동일한 사이즈의 어레이 생성, -1로 초기화하여 오큰수 저장

 

입력받은 수열을 어레이에 저장하고, 크기가 같은 어레이를 생성하여 -1로 초기화 함.

수열의 인덱스0부터 반복문을 돌며 스택에 인덱스를 저장함.

스택의 최상단 인덱스에 해당하는 수보다 큰 수가 나타나면,

이 수가 오큰수가 되므로, 오큰수를 새로 생성한 어레이의 최상단 인덱스에 저장한다.

오큰수를 찾으면 스택에서 뺀다.

 

이 방법으로 한번만 반복문을 돌면 되므로, 시간복잡도 O(N)이다.

 

package com.company;
import java.io.*;
import java.util.*;

public class BOJ17298 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Stack<Integer> st=new Stack<>();
        int t=sc.nextInt();
        int[] nums=new int[t];
        int[] NGE=new int[t];
        Arrays.fill(NGE, -1);

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

        for(int i=0;i<t;i++){
            int num=nums[i];
            if(st.empty()){
                st.push(i);
            }
            else{
                while(nums[st.peek()]<num){
                    NGE[st.pop()]=num;
                    if(st.empty())
                        break;
                }
                st.push(i);
            }
        }

        for(int i=0;i<t;i++){
            bw.write(NGE[i]+" ");
        }
        bw.flush();
    }

}