C++で2D座標点を出現頻度付きで昇順に出力する方法

この問題では、2次元平面上の点の座標を表す2つの配列 x[] と y[] が与えられます。ここで、(x, y) の組み合わせが1つの点の座標に対応します。求められているのは、すべての点をその出現頻度とともに昇順で出力することです。

問題の例

入力と出力の例を見て、問題の内容を具体的に理解しましょう。

入力: x[]={0, 1, 1, 0, 0} ; y[]={1, 2, 2, 2, 1}
出力:
(0, 1) = 2
(0, 2) = 1
(1, 2) = 2

この例では、点 (0, 1) と点 (1, 2) がそれぞれ2回出現しており、点 (0, 2) は1回だけ出現しています。

解決のアプローチ

この問題を解くには、各点の出現頻度を効率的に記録する必要があります。そこで活躍するのが map（連想配列） というデータ構造です。

• キー： 点の座標 (x[i], y[i]) を pair<int, int> 型として格納
• 値： その点が出現した回数（整数）

C++の map はキーを自動的にソートして保持するため、頻度の集計が完了すれば、そのまま昇順で出力できます。別途ソート処理を追加する必要がないのが大きなメリットです。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

void printFrequencyofPoint(int x[], int y[], int n){
    map<pair<int, int>, int> pFreq;
    // 各点の出現頻度をカウント
    for (int i = 0; i < n; i++)
        pFreq[make_pair(x[i], y[i])]++;
    // 昇順に並んだ結果を出力
    map<pair<int, int>, int>::iterator i;
    for (i = pFreq.begin(); i != pFreq.end(); i++) {
        cout << "(" << (i->first).first << ", " << (i->first).second << ") -> ";
        cout << i->second << "\n";
    }
}

int main() {
    int x[]={0, 1, 1, 0, 0};
    int y[]={1, 2, 2, 2, 1};
    int n=5;
    cout << "各点とその出現頻度:\n";
    printFrequencyofPoint(x, y, n);
    return 0;
}

実行結果

各点とその出現頻度:
(0, 1) -> 2
(0, 2) -> 1
(1, 2) -> 2

コードの解説

1. 頻度のカウント

ループで各座標を順番に処理し、pFreq[make_pair(x[i], y[i])]++ によって該当する点のカウントを1ずつ増やします。map に存在しないキーにアクセスすると自動的に値が0で初期化されるため、この簡潔な書き方がそのまま使えます。

2. 結果の出力

map のイテレータを先頭から末尾まで走査することで、座標が昇順に並んだ状態で各点とその出現頻度を出力できます。

計算量の分析

• 時間計算量： O(n log n) — n個の点をそれぞれ map に挿入する際、1回あたり O(log n) の処理が必要なため
• 空間計算量： O(n) — 最大で n 個の異なる点を map に格納するため

このように、map を活用すれば頻度の集計と昇順ソートを一度に行うことができ、非常に効率的な実装が可能です。