[JAVA] 백준 17298번- 오큰수

https://www.acmicpc.net/problem/17298

17298번: 오큰수

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        int[] answer = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());

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

        Stack<Integer> stack = new Stack<>();

        for(int i=n-1; i>=0; i--){
            while(!stack.isEmpty() && stack.peek() <= arr[i]){ // 스택이 비어있지 않고 스택의 top이 수열 값보다 작다면
                stack.pop();
            }
            if(stack.isEmpty()) answer[i] = -1; // 수열 값보다 큰 스택의 top 값이 없으면
            else answer[i] = stack.peek(); // 스택의 top 이 수열 값보다 크면 스택의 top 값 기록

            stack.push(arr[i]); // 스택에 수열 값 저장
        }

        for(int x : answer){
            sb.append(x).append(" ");
        }

        System.out.println(sb);
    }
}

 

 

처음에 이중 for문 (시간 복잡도 O(N^))으로 했다가 당연히 시간초과가 났다. 

위와 같은 방법으로 스택을 사용 하면 시간 복잡도 O(N)으로 시간초과 없이 풀 수 있다.

입력받은 수열을 arr 배열에 넣고, 배열의 오른쪽부터 탐색한다.

스택에 수열 값을 넣고, 스택이 비게되거나 스택의 top이 현재 수열 값보다 클 때까지 스택을 pop한다.

그렇게 해 스택이 모두 비워지게 된다면 오큰수가 없는 것이므로 -1을 기록하고,

수열 값보다 큰 스택의 top 값을 만나면 그 값을 기록한다.