백준 17298 자바

<문제>

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

17298번: 오큰수

 

<풀이>

n의 크기를 보면 O(n^2)으로 풀면 시간초과가 걸리는 문제인 것을 생각을 해야 한다.

해당 문제는 stack을 활용해서 문제를 푼다.

우선 스택에 첫 번째 값의 index를 넣는다. 그 후 다음 숫자가 스택의 peek()(인덱스)의 숫자와 비교를 한다. 만약 peek()가 크다면 비교하는 숫자의 index를 스택에 넣는다. 만약 비교하는 숫자가 크다면 해당 숫자보다 큰 숫자가 나올 때까지 pop을 한 후에 해당 숫자의 인덱스를 넣는다. 이때 스택에서 나오는 인덱스 위치의 배열 값에 비교한 값을 대입한다.

반복문이 종료되었을 때, 스택에 남아있는 값은 오큰수가 없는 숫자 이므로 해당 위치에 -1을 대입하고 배열을 출력한다.

 

<코드>

import java.util.*;
import java.io.*;

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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Stack<Integer> stack = new Stack<>();

        for(int i  = 0; i < n; i++) {
            while(!stack.empty() && 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++) {
            sb.append(arr[i]).append(" ");
        }
        System.out.println(sb.toString());


    }
}