뒤에 있는 큰 수 찾기_복습

2026.08.09

문제 풀이

나의 코드

---

소요 시간: 14분
시간 복잡도: $O(n)$

---

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int[] solution(int[] numbers) {
        int len = numbers.length;
        int[] result = new int[len];
        
        Deque<int[]> stack = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            while(!stack.isEmpty() && numbers[i] > stack.peek()[1]) {
                int[] arr = stack.pop();
                result[arr[0]] = numbers[i];
            }
            stack.push(new int[]{ i, numbers[i] });
        }
        while(!stack.isEmpty()) {
            int[] arr = stack.pop();
            result[arr[0]] = -1;
        }
        
        return result;
    }
}

AI 코드

---

시간 복잡도: $O(n)$

---

코드 분석

단조 감소 스택(monotonic stack)을 사용한 동일한 알고리즘이지만,
하나의 배열과 top 변수를 사용하여,
원소마다 배열 객체를 생성하는 나의 코드의 단점을 개선하였다.

---

class Solution {
    public int[] solution(int[] numbers) {
        int n = numbers.length;
        int[] answer = new int[n];
        int[] stack = new int[n];   // 인덱스만 저장하는 배열 스택
        int top = 0;                // 스택 크기

        for (int i = 0; i < n; i++) {
            while (top > 0 && numbers[stack[top - 1]] < numbers[i]) {
                answer[stack[--top]] = numbers[i];
            }
            stack[top++] = i;
        }
        while (top > 0) {
            answer[stack[--top]] = -1;
        }

        return answer;
    }
}

문제 풀이 후기

가장 값이 적게 나가는 배열 활용을 1차로 생각해보고,
불가능하다고 생각되면 그 때 라이브러리를 활용해야겠다.