알고리즘 문제를 풀 때에나 혹은 실무에서도 종종 데이터 내에서 순차적으로 대소 비교를 해야하는 경우는 있다.
이런 문제를 풀 때에는 디자인 적으로 단일 값에 대해 스트림 내에서 가장 가까운 최솟값 / 최댓값을 찾는 것 뿐 아니라 전체 데이터에서 그 다음 나오는 가장 가까운 작은값 / 큰값을 찾아야할 때가 있게 된다.
가령 다음과 같은 배열이 있다고 해보자.
이 때 스트림 내에서 각 배열의 요소들에 대해 다음에 나오는(가장 가까운) 작은 값은 다음과 같이 매핑된다
위의 배열에서는 가장 가까운 작은값이 없다면 -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 알고리즘 형태로 외국에서 알려진 테크닉이기 때문에 머릿 속에 담아두고 꺼내어 쓰면 좋을 것 같드.
'DataStructure & Algorithm > Algorithm' 카테고리의 다른 글
| 반복문을 이용한 Tree 의 후위순회(Post-order Traversal) (0) | 2019.07.30 |
|---|---|
| 이진탐색트리 확인 알고리즘 (Binary Search Tree Verification Algorithm) (0) | 2019.06.14 |
| LRU Cache Algorithm 정리 (0) | 2019.06.13 |
| 다익스트라(Dijkstra) 알고리즘을 이용한 최단거리 구하기 (0) | 2019.05.26 |
| 알고리즘 풀이 시 자주 사용되는 bit 연산 모음 (0) | 2019.05.11 |
