ソート済み双方向連結リストで積が指定値xと等しくなるトリプルの個数を数えるC++プログラム

問題の概要

整数値を格納したソート済みの双方向連結リスト(doubly linked list)が与えられます。この課題の目標は、3つのノードのデータの積が指定された値xと等しくなるようなトリプル(三つ組)の個数を求めることです。

例えば、入力リンクリストが「3→4→1→2」でxが6の場合、積が6になるトリプルは(3, 1, 2)の1つだけなので、カウントは1となります。

入力例と出力例

例1

入力:

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

出力:

積が指定値xと等しくなるトリプルの個数: 3

説明: 該当するトリプルは以下の3つです。

(4, 5, 10)、(4, 5, 10)、(10, 10, 2)

例2

入力:

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

出力:

積が指定値xと等しくなるトリプルの個数: 3

説明: 該当するトリプルは以下の3つです。

(4, 3, 1)、(3, 1, 4)、(3, 2, 2)

プログラムで使用するアプローチ

この解法では、以下の手順でトリプルの個数を数えます。

• 連結リストのノードを構造体として定義します。構造体にはint型のデータ部と、自己参照型のnextポインタおよびprevポインタを持たせます。
• 関数insert_node(struct block** head, int data)は、指定されたデータを持つ新しいノードをリンクリストの先頭に追加します。
• 関数Product_x(struct block* head, int x)は、双方向連結リストの先頭へのポインタと整数xを受け取り、データ部の積がxとなるトリプルの個数を返します。
• 最初にカウント用変数countを0で初期化します。
• struct block型の3つのポインタtemp_1、temp_2、temp_3を用意します。
• temp_1をリンクリストの先頭に、temp_2をtemp_1の次のノードに、temp_3をtemp_2の次のノードにそれぞれ設定することで、最初の3つのノードを指す状態を作ります。
• これらのポインタを使って、リストの末尾まで全組み合わせを走査します。
• 3つのポインタが指す現在のデータの積がxと等しい場合((temp_1->data * temp_2->data * temp_3->data) == x)、countをインクリメントします。
• 走査が完了すると、条件を満たすトリプルの総数がcountに格納されています。
• 結果としてcountを返します。

コード例

#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, 100);
    insert_node(&head, 16);
    insert_node(&head, 14);
    insert_node(&head, 10);
    insert_node(&head, 10);
    insert_node(&head, 2);
    int x = 200;
    cout<<"Count of triplets in a sorted doubly linked list whose product is equal to a given value x are: "<<Product_x(head, x);
    return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます。

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

まとめ

本記事では、ソート済みの双方向連結リストから、3ノードのデータの積が指定値xと一致するトリプルの個数を求める方法を解説しました。3重のネストしたループですべての組み合わせを調べるシンプルな手法のため、計算量はO(n³)となります。リストの要素数が多い場合は、ハッシュマップや双ポインタ(two pointer)技法を組み合わせることで、より効率的な実装も可能です。