프로그래머스: 뒤에 있는 큰 수 찾기(JAVA)

문제 설명

• 정수로 이루어진 배열 numbers가 주어집니다.
• 각 원소에 대해 자신보다 뒤에 있는 숫자 중에서 처음으로 자신보다 큰 수를 찾아야 합니다.
• 그런 수가 없다면 -1을 대신 넣습니다.

---

입력 예시

int[] numbers = {2, 3, 3, 5};

출력 예시

[3, 5, 5, -1]

 

---

풀이

이 문제는 단순히 이중 for문으로 O(N^2) 시간 복잡도로도 풀 수 있지만,
최적화가 필요한 경우 스택을 이용한 역순 순회 방식이 효율적입니다.

✅ 핵심 전략:

• 배열을 오른쪽 → 왼쪽으로 순회
• 자신보다 큰 수가 나올 때까지 스택 pop
• 조건을 만족하는 수를 만나면 answer에 저장하고 현재 수를 다시 push

---

Java 코드 (스택)

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--) {
            
            // 현재 수보다 작거나 같은 수는 필요 없음 (pop)
            while (!stack.isEmpty() && stack.peek() <= numbers[i]) {
                stack.pop();
            }
            
            // 스택이 비었다면 -1, 아니면 peek가 정답
            answer[i] = stack.isEmpty() ? -1 : stack.peek();
            
            // 현재 숫자를 스택에 push
            stack.push(numbers[i]);
        }
        
        return answer;
    }
}

 

시간 복잡도

• 시간복잡도: O(N)
  → 각 원소는 스택에 한 번 push, 한 번 pop만 되기 때문에 총 연산은 2N 이내입니다.