[programmers] 뒤에 있는 큰 수 찾기 - Java

정수 배열 numbers에서 각 원소에 대해 자신보다 뒤에 있는 가장 가까운 큰 수를 찾는 문제를 다루고 있다. 스택을 사용하여 효율적으로 해결하며, 각 원소를 처리하는 동안 현재 숫자보다 작거나 같은 숫자는 스택에서 제거한다. 최종적으로 시간 복잡도는 O(n)이다.

DriedPollack

Sep 16, 2024

Contents

뒤에 있는 큰 수 찾기 solution.java 핵심 키워드 결론!

뒤에 있는 큰 수 찾기

문제 설명

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.

정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

제한사항

4 ≤ numbers의 길이 ≤ 1,000,000

1 ≤ numbers[i] ≤ 1,000,000

입출력 예

numbers	result
[2, 3, 3, 5]	[3, 5, 5, -1]
[9, 1, 5, 3, 6, 2]	[-1, 5, 6, 6, -1, -1]

solution.java


import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int n = numbers.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = n - 1; i >= 0; i--) {
            // 스택에서 현재 숫자보다 작거나 같은 요소를 pop
            while (!stack.isEmpty() && stack.peek() <= numbers[i]) {
                stack.pop();
            }
            
            // 스택이 비어 있으면 오른쪽에 더 큰 숫자가 없음
            if (stack.isEmpty()) {
                result[i] = -1;
            } else {
                result[i] = stack.peek();
            }
            
            // 현재 숫자를 스택에 push
            stack.push(numbers[i]);
        }

        return result;
    }
}