[프로그래머스] 뒤에 있는 큰 수 찾기 JAVA

문제

문제 해결

처음에는 이중 for문으로 접근하였지만 역시나 시간복잡도가 높아져 실패했다.
이후에 스택을 사용하여 문제를 해결했다.
스택을 이용하여 배열을 역순으로 처리하면서 현재 숫자보다 큰 값을 찾으면 된다.

1. 역순으로 배열 처리: numbers의 뒤에서 부터 접근한다.
2. 스택에서 작은값 제거 : 스택이 비어있지 않고, stack.peek()가 현재 수보다 클때까지 pop()
3. 뒷 큰 수 결정 : 스택이 비어있다면 (현재 수 뒤로 큰 숫자가 없음) answer에는 -1을 저장
4. 뒷 큰 수 결정 : 스택이 비어있지 않다면 가장 상단의 숫자(stack.peek())를 answer에 저장
5. 스택에 현재 숫자 추가: 현재 숫자를 스택에 push

코드

import java.util.*;

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

        // 배열을 역순으로 처리
        for (int i = numbers.length - 1; i >= 0; i--) {
            // 스택에서 현재 숫자보다 작거나 같은 값 제거
            while (!stack.isEmpty() && stack.peek() <= numbers[i]) {
                stack.pop();
            }

            // 뒷 큰 수 결정
            if (stack.isEmpty()) {
                answer[i] = -1;
            } else {
                answer[i] = stack.peek();
            }

            // 현재 숫자를 스택에 추가
            stack.push(numbers[i]);
        }

        return answer;
    }
}