[JAVA] 백준 17298 큐

 

 

 

 

 

 

17298번: 오큰수

문제

자신을 기준으로 우측에 있는 수열들 중 가장 가까운 값을 오큰수라고 한다.

각 수열을 기준으로 모든 오큰수를 출력하세요.

풀이

수열을 모두 배열에 저장한다.

수열 전체를 반복하는데 만약 현재 수열보다 작은 수를 가진 인덱스가 있다면 오큰수 배열에 현재 값을 넣고 pop해준다.

그리고 현재 인덱스를 큐에 담는다.

만약 오큰수 배열에 0이 들어 있다면 오큰수가 없는 것이므로 -1을 출력하고

오큰수가 있다면 오큰수를 출력한다.

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

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

        Stack<Integer> stack = new Stack<>();
        for(int i=0; i<N; i++){
            int target = A[i];
            while(!stack.isEmpty() && A[stack.peek()] <target){
                NGE[stack.pop()] = target;
            }
            stack.push(i);
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++){
            if(NGE[i] == 0) sb.append("-1 ");
            else sb.append(NGE[i]).append(" ");
        }
        System.out.println(sb);
    }
}

결과