단일 연결 리스트(singly linked list)와 정수 k가 주어졌을 때, (n/k)번째 요소를 찾는 함수를 작성해야 합니다. 여기서 n은 리스트에 포함된 전체 노드의 개수입니다. 계산 결과가 소수로 나올 경우에는 올림(ceil) 값을 사용합니다.
예를 들어 리스트가 1 → 2 → 3 → 4 → 5 → 6이고 k = 2라고 가정해 보겠습니다. 이때 n = 6, k = 2이므로 n/k = 6/2 = 3, 즉 세 번째 노드의 값인 3이 출력됩니다.
해결 접근 방법
이 문제는 두 개의 포인터를 활용한 간단한 순회 기법으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 두 개의 포인터 temp와 fracPoint를 선언하고, 각각 NULL과 시작 노드(start)로 초기화합니다.
- temp 포인터가 k개의 노드를 지날 때마다 fracPoint 포인터를 한 칸씩 앞으로 이동시킵니다.
리스트를 한 번만 순회하면서 인덱스 i를 기준으로 i % k == 0인 시점마다 fracPoint를 이동시키면, 최종적으로 fracPoint는 n/k번째 노드를 가리키게 됩니다.
구현 예제 (C++)
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
};
Node* getNode(int data) {
Node* new_node = new Node;
new_node->data = data;
new_node->next = NULL;
return new_node;
}
Node* fractionalNodes(Node* start, int k) {
if (k <= 0 || start == NULL)
return NULL;
Node* fracPoint = NULL;
int i = 0;
for (Node* temp = start; temp != NULL; temp = temp->next) {
if (i % k == 0) {
if (fracPoint == NULL)
fracPoint = start;
else
fracPoint = fracPoint->next;
}
i++;
}
return fracPoint;
}
void printList(Node* node) {
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
int main(void) {
Node* start = getNode(1);
start->next = getNode(2);
start->next->next = getNode(3);
start->next->next->next = getNode(4);
start->next->next->next->next = getNode(5);
int k = 2;
cout << "List is: ";
printList(start);
Node* answer = fractionalNodes(start, k);
cout << "\nFractional node is " << answer->data;
}실행 결과
List is: 1 2 3 4 5 Fractional node is 3
동작 원리 및 복잡도 분석
위 코드에서는 먼저 유효성 검사를 수행하여 k가 0 이하이거나 리스트가 비어 있는 경우 NULL을 반환합니다. 이후 temp 포인터로 리스트를 처음부터 끝까지 순회하면서, 현재 인덱스 i가 k의 배수일 때마다 fracPoint를 다음 노드로 이동시킵니다.
예제에서 리스트 길이 n = 5, k = 2인 경우, 인덱스 0, 2, 4에서 fracPoint가 이동하여 최종적으로 세 번째 노드(값 3)를 가리키게 됩니다. 이는 ⌈5/2⌉ = 3번째 노드와 일치합니다.
- 시간 복잡도: O(n) — 리스트를 한 번만 순회합니다.
- 공간 복잡도: O(1) — 추가 메모리 없이 포인터 두 개만 사용합니다.