문제 개요
연결 리스트(linked list)와 기준 값 x가 주어졌을 때, 리스트를 두 개의 파티션으로 나누는 문제를 생각해 보겠습니다. 조건은 다음과 같습니다.
- x보다 작은 값을 가진 노드들은 모두 앞쪽에 위치해야 합니다.
- x보다 크거나 같은 값을 가진 노드들은 그 뒤에 위치해야 합니다.
- 두 파티션 각각 안에서는 원래 노드들의 상대적인 순서가 그대로 유지되어야 합니다.
예를 들어 리스트가 [1,4,3,2,5,2]이고 x = 3이라면, 출력은 [1,2,2,4,3,5]가 됩니다.
해결 전략: 더미 노드 활용
이 문제는 더미(dummy) 노드 두 개를 사용하면 깔끔하게 해결할 수 있습니다. 하나는 x보다 작은 노드들을 모으는 리스트용이고, 다른 하나는 x보다 크거나 같은 노드들을 모으는 리스트용입니다. 순회가 끝난 후 두 리스트를 이어 붙이면 원하는 결과를 얻을 수 있습니다.
알고리즘 단계
- -1로 초기화된 더미 노드 d1과 d2를 생성하고, 각각을 가리키는 포인터 dp1과 dp2를 만듭니다.
- a가 NULL이 아닌 동안 다음을 반복합니다.
- a의 값이 기준값보다 작으면 → dp1 뒤에 a의 값을 가진 새 노드를 연결하고, dp1을 한 칸 앞으로 이동합니다.
- 그렇지 않으면 → dp2 뒤에 a의 값을 가진 새 노드를 연결하고, dp2를 한 칸 앞으로 이동합니다.
- a를 다음 노드로 이동시킵니다.
- 반복이 끝나면 dp1의 next를 d2의 next로 설정하여 두 리스트를 연결합니다.
- d1의 next를 반환합니다.
C++ 구현 예제
아래 코드를 통해 실제 구현을 확인해 보겠습니다.
#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->next){
cout << ptr->val << ", ";
ptr = ptr->next;
}
cout << "]" << endl;
}
class Solution {
public:
ListNode* partition(ListNode* a, int b) {
ListNode* dummy1 = new ListNode(-1);
ListNode* dummy2 = new ListNode(-1);
ListNode* dummyPtr1 = dummy1;
ListNode* dummyPtr2 = dummy2;
while(a){
if(a->val < b){
dummyPtr1->next = new ListNode(a->val);
dummyPtr1 = dummyPtr1->next;
}
else{
dummyPtr2->next = new ListNode(a->val);
dummyPtr2 = dummyPtr2->next;
}
a = a->next;
}
dummyPtr1->next = dummy2->next;
return dummy1->next;
}
};
main(){
Solution ob;
vector<int> v = {1,4,6,3,2,5,2,8};
ListNode *head = make_list(v);
print_list(ob.partition(head, 3));
}입력 / 출력
[1,4,6,3,2,5,2,8] 3
[1, 2, 2, 4, 6, 3, 5]
결과 해설
기준값 3보다 작은 노드들(1, 2, 2)이 앞쪽에, 3 이상인 노드들(4, 6, 3, 5, 8)이 뒤쪽에 배치되었으며, 각 그룹 내에서 원래의 상대적 순서가 그대로 유지된 것을 확인할 수 있습니다.
참고로 위 출력에서 마지막 노드(8)가 표시되지 않는 것은 partition 함수의 문제가 아니라, print_list 함수가 while(ptr->next) 조건으로 인해 마지막 노드를 건너뛰기 때문입니다. 실제 결과 리스트는 [1, 2, 2, 4, 6, 3, 5, 8]입니다.
복잡도 분석
- 시간 복잡도: O(n) — 리스트를 한 번만 순회하면 됩니다.
- 공간 복잡도: O(n) — 각 노드마다 새 노드를 생성하기 때문입니다. 기존 노드를 재사용하도록 포인터만 재배치하면 추가 공간을 O(1)까지 줄일 수 있습니다.