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

 

 

조건 : 4 ≤ numbers의 길이 ≤ 1,000,000

위 조건때문에 시간 복잡도가 O(n^2)가 되면 타임아웃이 납니다. 따라서 이중포문 사용하면 안됨

 

public class Main {
    public static void main(String[] args) {
        int[] numbers = {9, 1, 5, 3, 6, 2};
        int[] res = solution(numbers);

        for (int r : res) {
            System.out.print(r);
        }
    }

    public static int[] solution(int[] numbers) {
        int N = numbers.length;

        int[] results = new int[N];
        Stack<Integer> stack = new Stack();

        stack.push(numbers[N - 1]);

        for (int i = N - 2; i >= 0; i--) {
            int number = numbers[i];

            if (number < numbers[i + 1]) {
                results[i] = numbers[i + 1];
                stack.push(numbers[i + 1]);
            } else {
                while (!stack.empty()) {
                    int tmp = stack.pop();
                    if (tmp > number) {
                        results[i] = tmp;
                        stack.push(tmp);
                        break;
                    }
                }

                if (results[i] == 0)
                    results[i] = -1;
            }
        }

        results[N - 1] = -1;
        return results;
    }
}