뒤에 있는 큰 수 찾기

📝 문제

프로그래머스

 

🔥 시도해본 접근 방식

1. 완전 탐색

처음에는 문제가 보이는대로 처음부터 끝까지 완전탐색으로 접근해보았다.

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

        for (int i = 0; i < numbers.length; i++) {
            answer[i] = -1; // 초기화

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

        return answer;
    }
}

코드 자체는 의외로 쉽게 나왔으나 테스트 케이스 20번부터 시간초과가 발생했다.

시간 복잡도를 줄일 수 있도록 접근 방식 변경이 필요했다.

많은 시간을 투자 했으나 결국 방법이 떠오르지 않아서 구글링을 했고,

원리를 이해하는데 시간이 꽤 걸렸다. 참고한글

2. NSR / NSL 알고리즘

가장 가까이 있는 수를 찾는 알고리즘을 NSR/NSL 이라고 부르는 것 같다.

핵심은 Stack을 사용하고, 뒤에서부터 탐색하여 가장 가까운 큰수가 될 수 있는 값들을 Stack에 push하고 의미 없는 값은 pop하면서탐색 범위를 줄이는 것이다.

*의미 없는 값: Stack에 후입된 값이 전입된 값보다 크거나 같을 때 때 전입된 값들

ex) {5, 4, 1, 2, 3, 4} 여기서 하이라이팅된 4, 1, 2, 3

 

✨ 성공 코드

import java.util.Stack;

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

        Stack<Integer> st = new Stack<>();

        for (int i = numbers.length - 1; i >= 0; i--) {
            answer[i] = -1; // 초기화

            while (!st.isEmpty()) {
                if (numbers[i] < st.peek()) {
                    answer[i] = st.peek();
                    break;
                } else {
                    st.pop();
                }
            }

            st.push(numbers[i]);
        }

        return answer;
    }
}