[백준]17298_오큰수

문제링크

풀이

 데이터를 순회하면서 현재 스택이 비어있다면 일단은 스택에 넣는다.
 스택에는 현재 인덱스값을 저장한다.
 스택에 있는 값을 peek() 해서 현재 값과 비교를 한다.
 
 만약 현재값이 더 크다면, 현재값이 스택에있는 arr[index]값의 오큰수가 된다.
 이는 순차적으로 데이터를 조회하기 때문에 현재값이 더 크다면 스택에 있는 값보다 오른쪽이면서 큰값중
 첫번째 위치한 값이된다.
 이 과정을 스택에 있는 top값이 현재값보다 크거나 없으면 멈춰야한다.
 그래서 스택에 값이 비어있지않을 때를 while문 조건으로한다.
 while문을 탈출하는 조건중 스택이 빈경우도 있지만, 현재값이 top값보다 작은 경우도 포함한다.
 그다음 현재값을 스택에 넣어준다.
 
 마지막으로 스택에 있는 값은 오큰수가 없는 값들의 인덱스를 뜻하게 된다.
 ans[stack.pop()] = -1 | 그래서 해당 위치를 -1을 입력해준다.

이 풀이로 앞에서 처리된 값들을 제외하고 연산할 수 있어서 시간복잡도를 줄일 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class BJ_17298_오큰수 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        int[] ans = 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 = 0; i < n; i++) {
            if (stack.isEmpty()) {
                stack.add(i);
            } else {
            // 빈 스택 아니고, 현재값이 이전에 넣은 값보다 더 큰 경우만 처리.
                while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                    ans[stack.peek()] = arr[i]; // 오큰수 기록
                    stack.pop(); // 오큰수 처리된거 빼기.
                }
                stack.add(i); // 현재 값 스택에 넣어줌.
            }
        }

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

        StringBuilder sb = new StringBuilder();
        for (int num : ans) {
            sb.append(num + " ");
        }

        System.out.println(sb);

    }
}

 

[참고자료]
https://www.devkuma.com/docs/data-structure/stack/ (이미지)
https://youtu.be/rK8lUhjKWvc?si=m4sd23vOH5EA8Klp (풀이)