[백준 17298, Java] 오큰수

문제

www.acmicpc.net/problem/17298

17298번: 오큰수

 

풀이

1. 순회 (시간초과)

- 오큰수를 순회로 풀면 시간 초과가 난다. 즉 수열을 순회하면서 index번째 수의 오큰수를 구할 때, 다시 index+1 부터 순회를 하게되면 시간 복잡도는 N제곱이 되어서 시간초과가 난다.

 

2. 스택이용

- A의 오큰수 B를 구하는 게 아닌, B가 어떤 수의 오큰수가 되는지를 역으로 구해야한다. 

- B가 A의 오큰수이면 A와 B사이의 수 중에서 B가 가장 큰 수인 것을 이용한다. 

- 스택에는 아직 오큰수를 구하지 못한 수열의 인덱스가 들어간다. 

- 솔직히 아무런 힌트가 주어지지 않으면 못풀 것 같다.

 

 

코드

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

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[] numArray = new int[N];
        int[] oNum =  new int[N];
        Stack<Integer> stack = new Stack<>();

        st = new StringTokenizer(br.readLine(), " ");
        for(int index = 0; index<N; index++){
            numArray[index] = Integer.parseInt(st.nextToken());
        }

        for(int index = 0 ;index<numArray.length; index++){
            int num = numArray[index];

            while(!stack.isEmpty()){
                if(numArray[stack.peek()]<num){
                    oNum[stack.pop()] = num;
                }
                else{
                    break;
                }
            }
            stack.push(index);
        }

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

        for(int index = 0; index<oNum.length; index++){
            bw.write(String.valueOf(oNum[index])+" ");
        }
        bw.flush();
        bw.close();

    }
}