[백준] 201 - 자료구조 1 (연습) : 오큰수 (!) (17298번 JAVA)

[백준] 201 - 자료구조 1 (연습) : 오큰수 (17298번 JAVA)

---

[중첩 for 문을 사용한 풀이]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main{

    public static int[] arr;
    public static Stack<Integer> stack = new Stack<>();
    public static int N;
    
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=0; i<N; i++){
            sb.append(NGE(i)).append(" ");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    public static int NGE(int i){
        for(int j=i+1; j<N; j++){
            stack.push(arr[j]);
        }

        int oks = -1;

        for(int j=i+1; j<N; j++){
            int val = stack.pop();
            if (val > arr[i]){
                oks = val;
            }
        }
        return oks;
    }

}

=> 시간초과 발생

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Stack<Integer> stack = new Stack<>();
        
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

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

        for(int i=0; i<N; i++){
            
            while(!stack.isEmpty() && arr[stack.peek()] < arr[i]){
                arr[stack.pop()] = arr[i];
            }

            stack.push(i);
        }

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

        for(int i=0; i<N; i++){
            bw.write(arr[i] + " ");
        }

        bw.flush();
        bw.close();
    }
}