가장 가까운 작은값 찾기 (NSR / NSL 알고리즘)

 

알고리즘 문제를 풀 때에나 혹은 실무에서도 종종 데이터 내에서 순차적으로 대소 비교를 해야하는 경우는 있다.

이런 문제를 풀 때에는 디자인 적으로 단일 값에 대해 스트림 내에서 가장 가까운 최솟값 / 최댓값을 찾는 것 뿐 아니라 전체 데이터에서 그 다음 나오는 가장 가까운 작은값 / 큰값을 찾아야할 때가 있게 된다.

 

가령 다음과 같은 배열이 있다고 해보자.

 

이 때 스트림 내에서 각 배열의 요소들에 대해 다음에 나오는(가장 가까운) 작은 값은 다음과 같이 매핑된다

위의 배열에서는 가장 가까운 작은값이 없다면 -1 이라고 표시했다. 

배열 내에서 단일 요소에 대해서라면 가장 가까운 작은 값을 구하는건 어려운 일이 아니다.

하지만 전체 배열, 실무에서라면 전체 데이터 셋에서 가장 가까운 작은값 / 큰값을 찾는 데에는 시간 복잡도를 생각해야되게 된다.

 

가장 간단히 백트래킹으로 한다면 이는 O(n^2) 의 시간 복잡도로 해결할 수가 있다.

즉, 위의 그림에 색깔별 화살표 모양으로 나타난대로 각 요소별로 배열을 전체 순회하면서 나오는 첫번째 상대값을 찾아 배열에 저장하면 되는 것이다.

 

하지만 늘 그렇듯 O(n^2) 의 알고리즘은 데이터 사이즈가 커질수록 부담스러운 알고리즘이 된다.

 

스택을 이용한다면 이에 대해서 O(n) 의 시간복잡도를 갖는 최적 알고리즘을 설계할 수가 있다.

알고리즘은 다음과 같이 동작한다.

왼쪽에서 오른쪽으로 훑으면서 가장 가까운 작은/큰 값을 찾아야하기 때문에 반대로 오른쪽에서 왼쪽으로 스위핑하는 알고리즘을 설계하고, 각 요소를 스택에 담는다.

각 요소들을 검사하면서 스택에서 조건에 만족하지 않는 요소들은 Pop 해주고, 자기 자신을 Push 해준다.

다음 코드를 참고해본다.

public class Solution {
    private int[] nearestSmallerToRight(int[] nums) {
        // [4,5,2,10,8]
        // [2,2,-1,8,-1]
        int[] solve = new int[nums.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() >= nums[i]) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                solve[i] = -1;
            } else {
                solve[i] = stack.peek();
            }
            stack.push(nums[i]);
        }
        return solve;
    }
}

이와 같은 알고리즘은 비단 데이터셋 내에서 가장 근사한 작은/큰 값을 찾는 것 뿐 아니라 조건에 맞는 근사값을 찾는 데에도 상당히 유용하게 쓸 수 있는 알고리즘이다.

 

실무에서도 생각 안하고 코딩을 할 뿐 데이터 셋에 따라 성능에 영향을 줄 수 있을만한 포인트이기 때문에 생각해보는 것이 좋다. :) 

특히 코딩 인터뷰를 준비하고 있다면, 국내에는 주로 BFS 나 DFS 와 같은 백트래킹 중심의 알고리즘이 면접에 나오지만, 외국계 기업들에서는 시간 복잡도와 밀접한 코드 설계를 물어보는 경우가 많다.

이 개념 역시 NSR / NSL 알고리즘 형태로 외국에서 알려진 테크닉이기 때문에 머릿 속에 담아두고 꺼내어 쓰면 좋을 것 같드.