C++ 이중 연결 리스트에서 주어진 합이 되는 쌍 찾기

이 문제에서는 이중 연결 리스트(doubly linked list)와 하나의 합(sum) 값이 주어지며, 연결 리스트 안에서 두 노드 값의 합이 주어진 합과 일치하는 모든 쌍(pair)을 찾아야 합니다.

문제 이해를 위한 예시

입력

head − 2 <-> 5 <-> 6 <-> 9 <-> 12
x = 11

출력

(2, 9), (5, 6)

설명

쌍 (2, 9): 2 + 9 = 11
쌍 (5, 6): 5 + 6 = 11

해결 방법 1: 중첩 반복문(브루트 포스)

가장 단순한 방법은 연결 리스트 전체를 순회하면서 요소를 하나씩 선택하고, 나머지 부분의 리스트에서 그 요소와 더했을 때 sum이 되는 값을 찾는 것입니다. 이는 중첩 반복문(nested loop)으로 구현할 수 있습니다.

다만 이 방법은 시간 복잡도가 O(n²)이므로 리스트가 길어질수록 비효율적이라는 단점이 있습니다.

구현 예제

#include<iostream>
using namespace std;
struct Node {
    int data;
    struct Node *next, *prev;
};
void findSumPairs(struct Node *head, int sum) {
    struct Node *first = head;
    int pairCount = 0;
    while (first != NULL) {
        struct Node *second = first -> next;
        while(second != NULL){
            if ((first->data + second->data) == sum) {
                pairCount++;
                cout<<"("<<first->data<<",
                "<<second->data<<")\n";
            }
            second = second -> next;
        }
        first = first -> next;
    }
    if (!pairCount)
        cout<<"No Such Pairs found !";
}
void insert(struct Node **head, int data) {
    struct Node *temp = new Node;
    temp->data = data;
    temp->next = temp->prev = NULL;
    if (!(*head))
        (*head) = temp;
    else{
        temp->next = *head;
        (*head)->prev = temp;
        (*head) = temp;
    }
}
int main() {
    struct Node *head = NULL;
    insert(&head, 12);
    insert(&head, 9);
    insert(&head, 6);
    insert(&head, 5);
    insert(&head, 2);
    int sum = 11;
    cout<<"Pair in the linked list with sum = "<<sum<<" :\n";
    findSumPairs(head, sum);
    return 0;
}

출력 결과

Pair in the linked list with sum = 11 :
(2, 9)
(5, 6)

해결 방법 2: 투 포인터(Two Pointer) 기법

연결 리스트가 정렬되어 있다는 특성을 활용하면 훨씬 효율적으로 문제를 해결할 수 있습니다. 이 방법에서는 두 개의 포인터를 사용하는데, 하나는 리스트의 머리(head)를 가리키는 start, 다른 하나는 마지막 노드를 가리키는 end로 초기화합니다.

그런 다음 두 포인터가 가리키는 값의 합(sumVal)을 계산하여 주어진 합과 비교합니다.

sumVal > sum 인 경우 → end 포인터를 왼쪽(prev)으로 이동
sumVal < sum 인 경우 → start 포인터를 오른쪽(next)으로 이동
sumVal == sum 인 경우 → 두 값을 출력하고, start는 오른쪽으로 이동

두 포인터가 서로 교차하면 반복을 종료합니다. 또한 찾은 쌍의 개수를 함께 세어서, 개수가 0이면 "No Such Pairs found !"를 출력합니다.

정렬된 리스트에서 이 방법은 O(n)의 시간 복잡도로 동작하기 때문에 첫 번째 방법보다 훨씬 빠릅니다.

구현 예제

#include<iostream>
using namespace std;
struct Node {
    int data;
    struct Node *next, *prev;
};
void findSumPairs(struct Node *head, int sum) {
    struct Node *start = head;
    struct Node *end = head;
    while (end->next != NULL)
        end = end->next;
    int pairCount = 0;
    while (start != NULL && end != NULL && start != end &&
    end->next != start) {
        if ((start->data + end->data) == sum) {
            pairCount++;
            cout<<"("<<start->data<<", "<<end->data<<")\n";
            start = start->next;
            end = end->prev;
        }
        else if ((start->data + end->data) < sum)
            start = start->next;
        else
            end = end->prev;
    }
    if (!pairCount)
        cout<<"No Such Pairs found !";
}
void insert(struct Node **head, int data) {
    struct Node *temp = new Node;
    temp->data = data;
    temp->next = temp->prev = NULL;
    if (!(*head))
        (*head) = temp;
    else{
        temp->next = *head;
        (*head)->prev = temp;
        (*head) = temp;
    }
}
int main() {
    struct Node *head = NULL;
    insert(&head, 12);
    insert(&head, 9);
    insert(&head, 6);
    insert(&head, 5);
    insert(&head, 2);
    int sum = 11;
    cout<<"Pair in the linked list with sum = "<<sum<<" :\n";
    findSumPairs(head, sum);
    return 0;
}

출력 결과

Pair in the linked list with sum = 11 :
(2, 9)
(5, 6)