문제 개요
양의 정수로만 구성된 단일 연결 리스트(singly linked list)가 하나 주어집니다. 이때 각 노드의 다음 포인터(next)가 자신의 값(val)만큼 앞쪽에 있는 노드를 가리키도록 변형된 연결 리스트를 찾아야 하며, 더 이상 도달할 수 있는 노드가 없으면 next는 null이 됩니다.
예를 들어 입력이 [2, 2, 3, 5, 9, 15, 3, 4]라면, 헤드부터 시작해 각 노드의 값만큼 앞으로 점프하며 방문하는 노드들을 따라가므로 출력은 [2, 3, 15]가 됩니다.
해결 전략
핵심 아이디어는 기존 연결 리스트의 모든 값을 먼저 배열에 옮겨 담은 뒤, 인덱스를 현재 노드의 값만큼 건너뛰며 새 리스트를 구성하는 것입니다. 단계별로 정리하면 다음과 같습니다.
값을 저장할 배열 v를 선언합니다.
node가 null이 아닌 동안 반복합니다.
현재 노드의 값을 v에 추가합니다.
node를 다음 노드로 이동시킵니다.
값이 0인 더미(dummy) 노드 ret을 생성합니다.
temp = ret으로 초기화하고, 인덱스 i = 0으로 설정합니다.
i가 v의 크기보다 작은 동안 반복합니다.
temp의 next를 값 v[i]를 가진 새 노드로 연결합니다.
temp를 다음 노드로 이동시킵니다.
i += v[i]로 인덱스를 점프시킵니다.
더미 노드 바로 다음인 ret->next를 결과로 반환합니다.
구현 코드
아래 예제를 통해 실제 동작을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class ListNode {
public:
int val;
ListNode *next;
ListNode(int data) {
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v) {
ListNode *head = new ListNode(v[0]);
for (int i = 1; i < v.size(); i++) {
ListNode *ptr = head;
while (ptr->next != NULL) {
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
void print_list(ListNode *head) {
ListNode *ptr = head;
cout << "[";
while (ptr) {
cout << ptr->val << ", ";
ptr = ptr->next;
}
cout << "]" << endl;
}
class Solution {
public:
ListNode* solve(ListNode* node) {
vector <int> v;
while(node){
v.push_back(node->val);
node = node->next;
}
ListNode* ret = new ListNode(0);
ListNode* temp = ret;
int i = 0;
while(i < v.size()){
temp->next = new ListNode(v[i]);
temp = temp->next;
i += v[i];
}
return ret->next;
}
};
main(){
Solution ob;
vector<int> v = {2,2,3,5,9,15,3,4};
ListNode *head = make_list(v);
print_list(ob.solve(head));
}
입력 및 실행 결과
{2,2,3,5,9,15,3,4}
[2, 3, 15]
동작 원리 상세 분석
배열 v = [2, 2, 3, 5, 9, 15, 3, 4]라고 할 때, 알고리즘이 어떻게 진행되는지 추적해 보겠습니다.
- 1단계: i = 0 → 값 2를 결과 리스트에 추가한 뒤, i = 0 + 2 = 2로 점프합니다.
- 2단계: i = 2 → 값 3을 추가한 뒤, i = 2 + 3 = 5로 점프합니다.
- 3단계: i = 5 → 값 15를 추가한 뒤, i = 5 + 15 = 20이 되어 배열 범위를 벗어나므로 반복이 종료됩니다.
따라서 최종 결과는 [2, 3, 15]입니다. 점프한 인덱스가 배열 크기를 초과하는 순간 탐색이 멈추고, 마지막 노드의 next는 자연스럽게 null이 되는 구조입니다.
시간·공간 복잡도
연결 리스트를 한 번 순회하는 데 O(n)이 걸리고, 점프 과정 역시 최악의 경우 O(n)이므로 전체 시간 복잡도는 O(n)입니다. 공간 복잡도는 값을 임시 저장하는 배열과 새로 생성되는 리스트 때문에 O(n)입니다.