[Algorithm] boj_18298 (Stack)

문제

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

접근

• 테스트 범위가 크기 때문에 단순 반복문이 아닌 다른 방법을 사용해야 한다.

• 문제에서 주어지는 오큰수란, 특정 인덱스의 이후 요소의 오큰수가 정해지지 않았을 경우 해당 인덱스의 오큰수도 정해지지 않는다는 점에서, LIFO 구조의 스택을 사용하여 반복문을 모두 순회하지 않을 수 있다.

1. 배열을 순회한다.

   • 이전 요소보다 작은 값일 경우 : stack에 해당 idx를 push
     (오큰수가 아니기 때문에)

   • 이전 요소보다 큰 값일 경우 : stack에서 idx를 차례로 peek 하면서 해당 배열 값(arr[idx])이 현재값보다 작다면 현재값(arr[i])으로 초기화시켜주고, pop

     	(stack에 들어있으면서, 현재값보다 작으면 현재값이 오큰수가 되기 떄문)

     현재값보다 크다면 스택 순회 stop (어차피 이전의 요소들은 현재값보다 크기 때문에 확인할 필요가 없다)

2. 배열을 모두 순회한 후 stack에 여전히 남아있는 수는 오큰수가 없는 것이므로 -1이 된다.

풀이

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

public class boj_17298_stack {

    static int N;
    static int[] arr;
    static Stack<Integer> stack;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        stack = new Stack<>();

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

        for (int i = 0; i < arr.length; i++) {
            //stack을 순회
            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                arr[stack.pop()] = arr[i];
            }

            stack.push(i);
        }

        //stack에 남아있는 값들은 오큰수가 없는 값의 인덱스이다 -> -1로 초기화
        while (!stack.isEmpty()) {
            Integer idx = stack.pop();
            arr[idx] = -1;
        }

        StringBuilder sb = new StringBuilder();
        for (int val : arr) {
            sb.append(val).append(" ");
        }

        System.out.println(sb);
    }
}