문제 정의
연결 리스트(Linked List)의 헤드(head)를 첫 번째이자 유일한 인수로 전달받아 처리하는 JavaScript 함수를 작성해야 합니다.
이 연결 리스트에는 숫자 데이터가 저장되어 있으며, 각 노드는 자신만의 '다음으로 큰 값(next larger value)'을 가질 수 있습니다. 노드 i에 대한 next_larger(node_i)는 다음 조건을 모두 만족하는 노드 j의 값입니다.
- j > i : 현재 노드보다 뒤에 위치한 노드여야 함
- node_j.val > node_i.val : 값이 현재 노드보다 커야 함
- 위 두 조건을 만족하는 j 중에서 가장 작은 인덱스를 선택
만약 이러한 j가 존재하지 않는다면, 해당 노드의 다음으로 큰 값은 0이 됩니다. 함수는 리스트를 순회하면서 각 요소에 대응하는 '다음으로 큰 요소'를 담은 배열을 생성하여 반환해야 합니다.
예를 들어, 연결 리스트가 다음과 같다고 가정해 보겠습니다.
그렇다면 기대되는 출력 결과는 다음과 같습니다.
const output = [7, 0, 5, 5, 0];
출력 결과 해설
2 바로 뒤에서 처음으로 등장하는 더 큰 값은 7이므로 2의 결과는 7입니다. 그 뒤에 7보다 큰 요소는 없으므로 0이 됩니다. 같은 방식으로 4와 3의 경우 뒤에서 처음으로 더 큰 값인 5가 결과가 되며, 마지막 노드 5보다 큰 값은 존재하지 않으므로 0이 됩니다.
예시 코드
먼저 연결 리스트를 구성하기 위한 Node 클래스와 LinkedList 클래스를 정의합니다.
class Node{
constructor(data){
this.data = data;
this.next = null;
};
};
class LinkedList{
constructor(){
this.head = null;
this.size = 0;
};
};
LinkedList.prototype.add = function(data){
const newNode = new Node(data);
let curr
if(this.head === null){
this.head = newNode;
}else{
curr = this.head;
while (curr.next) {
curr = curr.next;
}
curr.next = newNode;
};
this.size++;
};
이어서 실제 데이터를 삽입하고, 핵심 로직인 nextGreater 함수를 구현합니다.
const list = new LinkedList();
list.add(2);
list.add(7);
list.add(4);
list.add(3);
list.add(5);
const nextGreater = (head) => {
const arr = [];
const res = [];
let curr = head;
let currentIndex = 0
while(curr){
while (arr.length > 0 && curr.data > arr[arr.length - 1][1]) {
const [index] = arr.pop();
res[index] = curr.data;
};
arr.push([currentIndex, curr.data]);
currentIndex += 1;
curr = curr.next;
};
for(let i = 0; i < currentIndex; i++){
if(res[i] === undefined){
res[i] = 0;
};
};
return res;
};
console.log(nextGreater(list.head));
알고리즘 동작 원리
이 코드는 단조 감소 스택(monotonic decreasing stack) 아이디어를 활용한 효율적인 접근 방식입니다.
- 배열 arr에는 [인덱스, 노드 값] 형태의 쌍이 차례대로 저장됩니다.
- 새로운 노드를 순회할 때, 스택 최상단에 있는 값보다 현재 노드의 값이 더 크다면 해당 인덱스의 결과를 현재 값으로 확정하고 pop 합니다.
- 모든 순회가 끝난 후에도 결과 배열 res에서 undefined로 남아 있는 위치에는 0을 할당하여 '더 큰 값이 없음'을 표시합니다.
이 방식에서는 각 노드가 최대 한 번 push되고 한 번 pop되기 때문에 전체 시간 복잡도는 O(n)으로 매우 효율적입니다.
출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[ 7, 0, 5, 5, 0 ]