[Programmers] 뒤에 있는 큰 수 찾기

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

프로그래머스

문제 설명

스택을 활용하는 문제이다. 처음엔 이중 반복문에 break을 활용하여 해결하려 했으나 테스크 테이스 20~23에서 시간 초과가 발생하였고 이를 해결하기 위해 스택을 활용하여 해결했다.

스택

import java.util.Stack;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < numbers.length; i++) {
            while (!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
                int idx = stack.pop();
                answer[idx] = numbers[i];
            }
            stack.push(i);
            
            if (answer[i] == 0) {
                answer[i] = -1;
            }
        }

        return answer;
    }
}

이중 반복문

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] < numbers[j]) {
                    answer[i] = numbers[j];
                    break;
                }
            }
            
            if (answer[i] == 0) {
                answer[i] = -1;    
            }
        }
        
        return answer;
    }
}

차이점

막상 보면 둘 다 이중 반복문을 사용하고 있어 얼핏 보기에는 차이가 없어 보인다. 하지만 내부 동작을 살펴보면 차이점을 알 수 있다. 예제 입력은 [1, 1, 1, 5] 로 사용하겠다.

과정을 보면 이중 반복문은 한 요소에 대해서 큰 요소가 나올 때까지 모든 요소와 비교연산을 하기 때문에 O(n^2)의 시간 복잡도가 소요된다. 하지만 스택을 활용한 경우엔 각 요소마다 한 번의 비교와 push, pop을 사용하기 때문에 각 요소 순회 O(N) * O(1) = O(N)의 시간복잡도가 소요된다.