C++에서 곱이 주어진 값 x와 같은 정렬된 이중 연결 리스트의 세 쌍 개수 구하기

문제 소개

정수 값들을 담고 있는 정렬된 이중 연결 리스트(sorted doubly linked list)가 주어졌을 때, 세 노드 값의 곱이 주어진 값 x와 같아지는 세 쌍(triplet)의 개수를 찾는 것이 목표입니다.
예를 들어 연결 리스트가 3 → 4 → 1 → 2이고 x = 6이라면, (3, 1, 2)의 곱이 6이므로 조건을 만족하는 세 쌍은 1개입니다.

예제

예제 1

입력:

linked list: [ 200 → 4 → 16 → 5 → 10 → 10 → 2 ], x = 200

출력:

곱이 x와 같은 세 쌍의 개수: 3

설명: 조건을 만족하는 세 쌍은 (4, 5, 10), (4, 5, 10), (10, 10, 2)로 총 3개입니다. 리스트에 10이 두 개 있으므로 (4, 5, 10) 조합이 두 번 계산됩니다.

예제 2

입력:

linked list: [ 4 → 3 → 1 → 5 → 2 → 4 → 2 ], x = 12

출력:

곱이 x와 같은 세 쌍의 개수: 3

설명: 조건을 만족하는 세 쌍은 (4, 3, 1), (3, 1, 4), (3, 2, 2)로 총 3개입니다.

접근 방법

이 문제는 세 개의 포인터를 사용해 가능한 모든 세 쌍 조합을 탐색하는 브루트포스(brute force) 방식으로 해결할 수 있습니다. 알고리즘의 동작 과정은 다음과 같습니다.

정수형 data 필드와 자기 참조형 next, prev 포인터를 가지는 구조체(struct)로 연결 리스트 노드를 정의합니다.
insert_node(struct block** head, int data) 함수는 새 노드를 연결 리스트의 맨 앞(head)에 추가합니다.
Product_x(struct block* head, int x) 함수는 이중 연결 리스트의 head 포인터와 정수 x를 매개변수로 받아, 데이터 값의 곱이 x가 되는 세 쌍의 개수를 반환합니다.
초기 count 값은 0으로 설정합니다.
struct block 타입의 포인터 세 개(temp_1, temp_2, temp_3)를 선언합니다.
temp_1은 리스트의 첫 번째 노드에서, temp_2는 temp_1의 다음 노드에서, temp_3는 temp_2의 다음 노드에서 시작해 세 포인터가 서로 다른 노드를 가리키도록 합니다.
세 포인터를 리스트의 마지막 노드까지 순차적으로 이동시키며 모든 조합을 탐색합니다.
현재 가리키는 세 노드 데이터의 곱이 x와 같으면((temp_1->data * temp_2->data * temp_3->data) == x) count를 1 증가시킵니다.
탐색이 종료되면 count에는 조건을 만족하는 세 쌍의 총 개수가 저장되어 있으며, 이 값을 결과로 반환합니다.

세 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n³)이며, 추가적인 공간이 필요하지 않아 공간 복잡도는 O(1)입니다.

C++ 구현 예제

#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 Product_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, 4);
    insert_node(&head, 16);
    insert_node(&head, 5);
    insert_node(&head, 10);
    insert_node(&head, 10);
    insert_node(&head, 2);
    int x = 200;
    cout << "곱이 주어진 값 x와 같은 정렬된 이중 연결 리스트의 세 쌍 개수: " << Product_x(head, x);
    return 0;
}

실행 결과

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

곱이 주어진 값 x와 같은 정렬된 이중 연결 리스트의 세 쌍 개수: 3

insert_node 함수는 새 노드를 항상 맨 앞에 추가하므로, 최종 리스트는 2 → 10 → 10 → 5 → 16 → 4 → 200 순서가 됩니다. 이 리스트에서 곱이 200이 되는 세 쌍은 (4, 5, 10) 두 개와 (10, 10, 2) 하나로 총 3개이며, 예제 1의 결과와 일치합니다.