[백준 | Java] 17298 오큰수

내 풀이

처음엔 이 문제를 꼭 스택을 써서 풀어야하나 생각이 들었지만, 코드로 직접 모두 구현하기에는 복잡한 부분이 많고 예제처럼 수열 A가 9 5 4 8과 같이 큰 수가 가장 앞에 온다면 시간초과가 발생하게 된다.

이 부분을 해결하기 위해 stack을 임시 저장 공간으로 사용했다. 수열 A의 첫 번째 요소부터 해당하는 인덱스를 스택에 저장하고, 수열 A를 왼쪽에서 오른쪽으로 탐색하다가 스택의 peek 값보다 큰 값이 나타나게 되면 스택에 저장된 인덱스를 큰 값의 인덱스로 치환한다.
이렇게 하게 되면 스택 내에는 수열 A의 현재 i번째 요소보다 작은 요소들만 존재하게 되어 오큰수를 확인할 수 있다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        Stack<Integer> stack = new Stack<>();

        int N = Integer.parseInt(st.nextToken());
        int[] A = new int[N];
        int[] result = new int[N];

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

        for (int i = 0; i < N; i++) {
            // 스택의 peek과 i번째 숫자와 비교해서 i번째 숫자가 더 클 경우 스택에 있는 모든 인덱스를 i번째 숫자로 넣기
            while (!stack.isEmpty() && A[stack.peek()] < A[i]){
                int idx = stack.pop();
                result[idx] = A[i];
            }
            // i번째 숫자의 인덱스를 저장
            stack.push(i);
        }

        for(int i=0;i<N;i++){
            sb.append(result[i]);
            sb.append(" ");
        }
        System.out.println(sb);
    }
}