뒤에 있는 큰 수 찾기

2026.04.21

문제 설명

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

제한 사항

• 4 ≤ numbers의 길이 ≤ 1,000,000
• • 1 ≤ numbers[i] ≤ 1,000,000

입출력 예

문제 풀이

1차 실행 오류

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

---

당연히 안될 것 같다고 생각했지만 역시나 시간 초과 오류 발생
배열의 길이 제한이 1,000,000 이하이다 보니 최적화가 필요하다.

---

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        int index = 0;
        boolean isExist = false;
        for (int i = 0; i < numbers.length; i++) {
            isExist = false;
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[j] > numbers[i]) {
                    isExist = true;
                    answer[index++] = numbers[j];
                    break;
                }
            }
            if(!isExist) {
                answer[index++] = -1;
            }
        }
        return answer;
    }
}

AI 코드

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

---

stack을 이용하여 현재 값보다 큰 수를 찾을 때 까지 탐색하는 것이 아닌,
뒤에 큰 수가 오면 일괄적으로 해결하는 방법을 사용하였음

---

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

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