[BOJ] 17298 오큰수 - JAVA

1. 풀이

① stack.peek()과 nums[i] 비교

• stack.peek()이 더 작으면 pop시켜서 없애버린다.
• 자신보다 큰 수 중 가장 오른쪽에 있는 수를 찾기 때문에 마지막 ④를 수행하면 그 뒤의 비교와 영향 없음

② ①이 끝난 뒤 stack이 비어있다면 nums[i]보다 큰 수가 없는 것이므로 result[i]에 -1을 저장하고 다음 숫자를 비교한다.

③ stack이 비어있지않고 stack.peek()이 nums[i]보다 크다면 저장한다.

④ stack에 현재 nums[i]를 push하고 다음 숫자를 비교한다.

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

public class BOJ_17298_오큰수 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());
        StringTokenizer st = new StringTokenizer(in.readLine());

        //입력
        int[] nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        //탐색
        int[] result = new int[N];
        Stack<Integer> stack = new Stack<>();
        for (int i = N - 1; i >= 0; i--) {
            while (!stack.empty() && stack.peek() <= nums[i]) {
                stack.pop();
            }

            if (stack.empty()) {
                result[i] = -1;
            } else if (stack.peek() > nums[i]) {
                result[i] = stack.peek();
            }

            stack.push(nums[i]);
        }

        //출력
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(result[i]).append(" ");
        }

        System.out.println(sb);
    }
}

---

2. 결과

result 배열을 사용하지 않고 StringBuilder의 insert를 사용하니 시간초과가 났다. [이 글]에 정리해놓았다!