C++에서 주어진 값 x와 합이 같은 정렬된 이중 연결 리스트의 트리플렛 개수 세기

문제 소개

정수 값으로 구성된 정렬된 이중 연결 리스트가 주어졌을 때, 서로 다른 세 노드의 데이터 합이 주어진 값 x와 같아지는 트리플렛(triplet)의 개수를 구하는 것이 목표입니다.

예를 들어 연결 리스트가 3−4−1−2이고 x가 6이라면, 트리플렛 (3, 1, 2)의 합이 6이므로 개수는 1이 됩니다.

C++에서 주어진 값 x와 합이 같은 정렬된 이중 연결 리스트의 트리플렛 개수 세기

예제 1

입력:

linked list: [ 3−4−13−5−10−10−0 ], x = 20

출력:

합이 주어진 값 x와 같은 정렬된 이중 연결 리스트의 트리플렛 개수: 2

설명: 조건을 만족하는 트리플렛은 (3, 4, 13)과 (10, 10, 0) 두 가지입니다.

예제 2

입력:

linked list: [ 4−3−1−5−2−4−2 ], x = 8

출력:

합이 주어진 값 x와 같은 정렬된 이중 연결 리스트의 트리플렛 개수: 6

설명: 조건을 만족하는 트리플렛은 (4, 3, 1), (1, 5, 2), (3, 1, 4), (1, 5, 2), (4, 2, 2), (2, 4, 2)로 총 6가지입니다.

접근 방법

이 문제는 브루트 포스(Brute Force) 방식으로 해결할 수 있습니다. 세 개의 포인터를 사용하여 가능한 모든 노드 조합을 하나씩 확인하는 것입니다.

연결 리스트의 노드는 int형 데이터와 자기 참조형 next, prev 포인터를 가지는 구조체(struct)로 정의합니다.
insert_node(struct block** head, int data) 함수는 새 노드를 생성해 리스트의 맨 앞(head)에 삽입합니다.
sum_x(struct block* head, int x) 함수는 이중 연결 리스트의 head 포인터와 정수 x를 받아, 데이터 합이 x가 되는 트리플렛의 개수를 반환합니다.
초기 카운트(count)는 0으로 설정합니다.
struct block 타입의 포인터 세 개(temp_1, temp_2, temp_3)를 선언합니다.
temp_1은 리스트의 head에서 시작하고, temp_2는 temp_1의 다음 노드, temp_3는 temp_2의 다음 노드를 가리켜 처음 세 노드를 차례로 가리키도록 합니다.
세 개의 중첩 반복문으로 마지막 노드까지 순회하며 가능한 모든 조합을 검사합니다.
현재 가리키는 세 노드의 데이터 합이 x와 같으면((temp_1->data + temp_2->data + temp_3->data) == x) count를 1 증가시킵니다.
순회가 끝나면 count에는 조건을 만족하는 트리플렛의 총 개수가 저장되어 있으며, 이를 결과로 반환합니다.

세 개의 중첩 반복문을 사용하기 때문에 이 방법의 시간 복잡도는 O(n³)입니다.

예제 코드

#include <iostream>
using namespace std;
struct block{
    int data;
    struct block *next, *prev;
};
void insert_node(struct block** head, int data){
    struct block* ptr = new block();
    ptr->data = data;
    ptr->next = NULL;
    ptr->prev = NULL;
    if ((*head) == NULL){
        (*head) = ptr;
    } else {
        ptr->next = *head;
        (*head)->prev = ptr;
        (*head) = ptr;
    }
}
int sum_x(struct block* head, int x){
    int count = 0;
    struct block *temp_1, *temp_2, *temp_3;
    for (temp_1 = head; temp_1!= NULL; temp_1 = temp_1->next){
        for (temp_2 = temp_1->next; temp_2 != NULL; temp_2 = temp_2->next){
            for (temp_3 = temp_2->next; temp_3!= NULL; temp_3 = temp_3->next){
                if ((temp_1->data + temp_2->data + temp_3->data) == x){
                    count++;
                }
            }
        }
    }
    return count;
}
int main(){
    struct block* head = NULL;
    insert_node(&head, 200);
    insert_node(&head, 100);
    insert_node(&head, 16);
    insert_node(&head, 14);
    insert_node(&head, 10);
    insert_node(&head, 10);
    insert_node(&head, 2);
    int x = 22;
    cout<<"Count of triplets in a sorted doubly linked list whose sum is equal to a given value x are: "<<sum_x(head, x);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Count of triplets in a sorted doubly linked list whose sum is equal to a given value x are: 1

insert_node 함수는 항상 새 노드를 맨 앞에 삽입하기 때문에, 실제 리스트는 2−10−10−14−16−100−200 순서로 구성됩니다. 이 중 합이 22가 되는 트리플렛은 (2, 10, 10) 하나뿐이므로 결과로 1이 출력됩니다.