C++로 세 개의 연결 리스트에서 주어진 숫자와 같은 합을 가지는 삼중항 찾기

개요

이 글에서는 세 개의 연결 리스트(Linked List)가 있을 때, 각 리스트에서 하나씩 선택한 세 값의 합이 주어진 숫자와 일치하는 첫 번째 삼중항(triplet)을 찾는 C++ 프로그램을 작성해 보겠습니다.

가장 기본적인 접근 방법은 세 개의 중첩 반복문(nested loop)을 사용하여 가능한 모든 조합을 하나씩 검사하는 것입니다. 이 방법은 시간 복잡도가 O(n³)로 다소 높지만, 구현이 매우 간단하고 로직을 이해하기 쉽다는 장점이 있습니다.

문제 해결 단계

• 연결 리스트를 위한 노드(Node) 클래스를 정의합니다.
• 테스트용 더미 데이터로 연결 리스트 세 개를 생성합니다.
• 세 개의 중첩 반복문을 작성하여 각 연결 리스트의 끝까지 순회하면서 모든 요소 조합을 검사합니다.
  • 현재 위치한 세 요소의 합을 계산합니다.
  • 계산된 합을 주어진 숫자와 비교합니다.
  • 두 값이 일치하면 해당 요소들을 출력하고 모든 반복문을 종료합니다.

C++ 코드 예제

전체 소스 코드는 다음과 같습니다.

#include 
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

void insertNewNode(Node** head_ref, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    *head_ref = new_node;
}

void findTriplet(Node *head_one, Node *head_two, Node *head_three, int givenNumber) {
    bool is_triplet_found = false;
    Node *a = head_one;
    while (a != NULL) {
        Node *b = head_two;
        while (b != NULL) {
            Node *c = head_three;
            while (c != NULL) {
                int sum = a->data + b->data + c->data;
                if (sum == givenNumber) {
                    cout << a->data << " " << b->data << " " << c->data << endl;
                    is_triplet_found = true;
                    break;
                }
                c = c->next;
            }
            if (is_triplet_found) break;
            b = b->next;
        }
        if (is_triplet_found) break;
        a = a->next;
    }
    if (!is_triplet_found) {
        cout << "No triplet found" << endl;
    }
}

int main() {
    Node* head_one = NULL;
    Node* head_two = NULL;
    Node* head_three = NULL;

    insertNewNode(&head_one, 4);
    insertNewNode(&head_one, 3);
    insertNewNode(&head_one, 2);
    insertNewNode(&head_one, 1);

    insertNewNode(&head_two, 4);
    insertNewNode(&head_two, 3);
    insertNewNode(&head_two, 2);
    insertNewNode(&head_two, 1);

    insertNewNode(&head_three, 1);
    insertNewNode(&head_three, 2);
    insertNewNode(&head_three, 3);
    insertNewNode(&head_three, 4);

    findTriplet(head_one, head_two, head_three, 9);
    findTriplet(head_one, head_two, head_three, 100);

    return 0;
}

실행 결과

위 코드를 실행하면 아래와 같은 결과가 출력됩니다.

1 4 4
No triplet found

첫 번째 호출에서는 세 리스트에서 각각 1, 4, 4를 선택했을 때 합이 9가 되므로 해당 삼중항이 출력됩니다. 두 번째 호출에서는 합이 100이 되는 조합이 존재하지 않기 때문에 "No triplet found"라는 메시지가 출력됩니다.

시간 복잡도

위 알고리즘은 세 개의 연결 리스트를 모두 순회하므로, 각 리스트의 길이를 n1, n2, n3라고 할 때 시간 복잡도는 O(n1 × n2 × n3)입니다. 추가적인 자료구조를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 참고로, 두 번째 리스트를 정렬한 뒤 투 포인터(two pointer) 기법을 적용하거나 해시 맵을 활용하면 O(n²) 수준으로 성능을 개선할 수 있습니다.

마무리

이번 글에서는 세 개의 연결 리스트에서 주어진 합과 같은 삼중항을 찾는 방법을 살펴보았습니다. 내용에 대해 궁금한 점이 있다면 댓글로 남겨주세요.