📌 프로그래머스 - 뒤에 있는 큰 수 찾기

🔍 문제 설명

정수로 이루어진 배열 numbers가 주어집니다.
각 원소에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 찾습니다.
뒷 큰수가 존재하지 않는 경우 -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]`

🔑 문제 접근

❌ 처음 접근: 이중 반복문 (O(N²))

가장 먼저 떠오르는 방법은 각 숫자에 대해 뒤의 숫자들을 순차적으로 탐색하는 방식이었습니다.
하지만 이 방식은 최악의 경우 O(N²)으로 시간 초과가 발생했습니다.

예제 코드 (비효율적인 접근)

public int[] solution(int[] numbers) {
    int[] answer = new int[numbers.length];

    for (int i = 0; i < numbers.length - 1; i++) {
        int max = -1;
        for (int j = i + 1; j < numbers.length; j++) {
            if (numbers[j] > numbers[i]) {
                max = numbers[j];
                break;
            }
        }
        answer[i] = max;
    }
    answer[numbers.length - 1] = -1;

    return answer;
}

✅ 작은 입력에서는 정상적으로 동작하지만, numbers가 100만 개 이상이면 시간 초과 발생!

💡 스택을 활용한 O(N) 풀이

🔹 핵심 아이디어

뒤에서부터 탐색하면서 스택을 활용하여 해결
현재 숫자보다 작은 값들은 스택에서 제거 (어차피 필요 없음)
스택의 top이 현재 숫자의 뒷 큰수
없으면 -1

🛠 코드 구현

import java.util.Stack;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<Integer> stack = new Stack<>();
        
        // 마지막 원소는 항상 -1
        stack.push(numbers[numbers.length - 1]);
        answer[numbers.length - 1] = -1;
        
        for (int i = numbers.length - 2; i >= 0; i--) {
            int max = -1;
            
            // 스택의 top이 현재 숫자보다 작거나 같으면 pop
            while (!stack.isEmpty()) {
                if (stack.peek() > numbers[i]) {
                    max = stack.peek();
                    break;
                } else {
                    stack.pop();
                }
            }
            
            stack.push(numbers[i]); // 현재 원소를 스택에 추가
            answer[i] = max;
        }
        
        return answer;
    }
}

⏱ 시간 복잡도 분석

각 원소는 최대 한 번만 push & pop 되므로 O(N)
최적화 성공 🎉 (이전 O(N²) → O(N))

📌 정리

접근 방식	시간 복잡도	설명
이중 반복문	`O(N²)`	하나씩 비교 → 시간 초과
스택 활용	`O(N)`	뒷 큰수만 효율적으로 관리

💡 핵심 포인트

스택을 사용하면 불필요한 탐색을 줄일 수 있다!
뒤에서부터 탐색하며 뒷 큰수를 찾는 패턴을 기억하자!

Latest Docs