[Programmers] Level 2 :: 뒤에 있는 큰 수 찾기 Java 풀이

프로그래머스

numbers 배열이 주어진다. 우리가 구하고 싶은 값은 numbers[i]를 기준으로 [i+1 ... numbers.length] 사이에 있는 숫자중 가장 가까우면서 numbers[i]보다 큰 숫자이다.

제한이 100만이기 때문에 O(N), O(NlogN) 이내에 풀어야 할 것 같은데 logN은 이분탐색말고 떠오르지 않으니 그냥 O(N)으로 접근해보자. 뒤에 있는 숫자 중 하나를 채우는 것이기 때문에 딱봐도 뒤에서부터 무엇인가 하면 될것 같은 느낌이 든다. 그래서 뒤에서 부터 값을 채우도록 문제를 접근해보자.

[2, 3, 3, 5]가 주어지는데 이 배열을 뒤집어보자. 그러면 [5, 3, 3, 2]가 나온다. 이제 문제는 나보다 앞에 있는 숫자 중 가장 큰 숫자를 찾으면 된다고 해석할 수 있다. 그다음 O(N) 탐색을 진행하면서 정답을 구해야 하는데, 여기서 내림차순으로 지나온 숫자들을 관리하면 된다는 것을 알 수 있다. 그림을 그리면 아주 쉽게 파악이 되는데, 그리기는 조금 귀찮으므로.. 넘어가자.

왜냐하면 현재 numbers[i]의 뒤에 있는 숫자 중 numbers[i]보다 작은 숫자는 더이상 사용되지 않기 때문이다. numbers[i-1]이든, numbers[i-5]든 numbers[i]의 뒤에 있는 숫자 중 나보다 작은 숫자는 절대 정답의 후보가 될 수 없다.

그래서 스택에 지나온 숫자를 내림차순으로 관리해주고 매번 peek() 값을 구하면 된다. 

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        Stack<Integer> st = new Stack<Integer>();
        
        int[] answer = new int[numbers.length];
        for (int i=numbers.length-1; i>=0; i--) {
            int number = numbers[i];
            answer[i] = -1;
            while (!st.empty()) {
                int top = st.peek();
                if (top > number) {
                    answer[i] = top;
                    break;
                }
                st.pop();
            }
            st.add(number);
        }
        return answer;
    }
}