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

https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

고찰 과정

numbers의 최대 크기는 100만이므로 단순 이중 반복문을 활용하여 문제를 해결하려고 하면 시간초과가 발생합니다.

그래서 numbers의 index 정보를 담는 stack 자료구조를 활용하였습니다.

 

문제의 예시를 활용하여 설명하겠습니다. 예를 들어 다음과 같은 배열이 있다고 가정하겠습니다.

• numbers 배열: [9, 1, 5, 3, 6, 2]
• result 배열: [-1, 5, 6, 6, -1, -1]

numbers 배열은 문제에서 주어진 배열이고, result는 뒷 큰수의 결과 배열입니다. 문제를 보시면 아시겠지만 numbers 배열의 최종 결과 배열인 result를 반환해주어야 합니다.  result에서 -1은 뒷 큰수가 없다는 의미이고 다음과 같은 과정으로 뒷 큰수를 구할 수가 있습니다.

 

이렇게 과정을 구현하면 스택에 남아 있는 인덱스 값들은 뒷큰수가 존재하지 않는 값들의 모임이라는 것이 보장이 되며, 시간 복잡도 O(N)으로 문제를 해결할 수가 있습니다.

---

코드

import java.util.Stack;
import java.util.Arrays;

class Solution {
    
    private static final int NOTHING = -1;
    
    public int[] solution(int[] numbers) {
        int len = numbers.length;
        int[] answer = new int[len];
        Stack<Integer> stack = new Stack<>();
        
        Arrays.fill(answer, NOTHING);
        
        for (int i = 0; i < len; ++i) {
            while (isValid(stack, numbers, i)) {
                answer[stack.pop()] = numbers[i];
            }
            
            stack.push(i);
        }
        
        return answer;
    }
    
    private boolean isValid(Stack<Integer> stack, int[] numbers, int index) {
        return !stack.isEmpty() && numbers[stack.peek()] < numbers[index];
    }
}