17298번 오큰수

바킹독 문제집에 Stack 분류로 되어있어서 스택을 사용해서 풀어야한다는 건 알겠는데.. 도저히 어떻게 풀어야하는지 감이 잡히지 않아 다른 사람들의 풀이(코드x)를 본 후 코드로 구현하였다. 풀이 안봤으면 절대 못풀었을 듯한 느낌.. 골드 문제부터는 확실히 어떤 알고리즘이나 자료구조의 개념만 알고 있다고 풀 수 있는 문제는 아닌 듯하다. 개념을 어떻게 활용해야할 지 감이 잘 안잡힌다..

풀이

입력되는 수열은 int형 배열에 저장한다.
스택을 한 개 선언하고 N만큼 for 반복문을 돌면서 스택에는 오큰수를 찾지 못한 수열 요소의 인덱스를 저장한다.
스택에 요소가 존재하고, peek한 인덱스에 해당하는 수열의 값이 현재 비교하려는 배열의 값보다 작을 경우 오큰수를 찾았다고 판단 하고, 스택 안에 있는 모든 인덱스의 배열 값들을 현재 비교하는 배열의 값으로 업데이트 해준다.
for 반복문을 다 돌았는데 stack에 요소가 남아있다면, 오큰수를 찾지 못한 인덱스들이므로 해당 하는 배열 값들을 -1로 업데이트한다.

package BOJ;

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

/**
 * 스택에 들어가는 요소들은 아직 오큰수를 찾지 못한 요소들의 인덱스이다.
 */

public class sol17298 {
    static Stack<Integer> stack;
    static int[] arr;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        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 < N; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                arr[stack.pop()] = arr[i];
            }
            stack.push(i);
        }

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

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(arr[i]).append(" ");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}