プログラム学習記録【16日目】/map, queue

前回から、記事のタイトルにもその日学習したことのトピックを書いてみることにした。
理由は、僕の場合noteは学習の公開で3日坊主を脱却しメリハリを持っておく、という理由の他に、備忘録としても利用したいと考えているからである。
前回、問題で並び替えができるのは配列だった、というところまでは思い出したのだが、構文をど忘れしてしまっており、それを確認するため過去記事を読み返していたのだが、どの記事に書いてあるか全くわからず、1つ1つ読み込んでしまった、という失敗談に基づいての試みだ。
時間があれば過去の記事についてもタイトルの変更を行っていきたい。
前分が長文になりがちなのでさっさと今日の勉強を始めていこう。

3.03.STLのコンテナ

STL内のコンテナ型について
特定の値にある値が紐付いているようなデータを扱う場合、mapという関数を用いる。
宣言は以下の通り。

map<keyの型, valueの型> 変数名;

mapの変数を操作する方法は以下の通り。

変数[key] = value;  // 値を追加する
変数.erase(key);  // 値の削除
変数.at(key)  // 変数へのアクセス
変数.size()  // 変数の要素数を調べる

値を1つずつ追加し、追加した順で取り出す処理を行うデータ構造をキューという。
C++ではSTLにqueueが用意されている。
queueの操作は以下の通り。

queue<型> 変数名;  // 空のキューを宣言
変数.push(値);  // 要素を追加
変数.front()  // 先頭の要素へのアクセス
変数.pop();  // 先頭の要素を削除
変数.size()  // 要素数の取得
変数.empty() // キューが空ならtrueを返す

キューに追加した要素のうち、最も大きいものを取り出す処理を行うときには、優先度付きキューというデータ構造を用いる。
STLにpriority_queue を用いることができる。

priority_queue<型> 変数;  // 空のpriority_queueの宣言
変数.push(値);  // 要素を追加
変数.top()   // 最大の要素の取得
変数.pop()  // 最大の要素を削除
変数.size()  // 要素数の取得
変数.empty()  // 空ならtrueを返す

また、次のようにしてpriority_queueを宣言すると、値が小さい順に取り出されるようになる。

priority_queue<型, vector<型>, greater<型>> 変数;

EX23.最頻値

要素数Nの配列が与えられる。この配列の中の値のうち、出現回数が最も多い値とその出現回数を求めるプログラムを作る。出現回数が最大になる値は複数存在しないもの値する。
値 出現回数
の順で出力する。
今回もサンプルプログラムなしなので、やることを練ってみる。
はじめにやりたいことは配列に値を入れていくところ。

int N;
 cin >> N;
 vector<int> A(N);
 for (int i = 0; i < N; i++)
 {
   cin >> A.at(i);
 }

んで、mapをつかって値の紐付けをする。

map<int, int> most;
 for (int x : A)
 {
   if (most.count(x)) // もしすでに含まれているならインクリメント
   {
     most.at(x)++;
   }
   else // 含まれているなら1を追加
   {
     most[x] = 1;
   }
 }

最頻値を判断し、その回数を確認

 int max_most = 0; 
 int ans = -1; 
 for (int x : A) // 最頻値の最大値を保持し、その回数をカウント
 {
   if (max_most < most.at(x))
   {
     max_most = most.at(x);
     ans = x;
   }
 }

全体のプログラムは以下。

#include <bits/stdc++.h>
using namespace std;
int main()
{
 int N;
 cin >> N;
 vector<int> A(N);
 for (int i = 0; i < N; i++)
 {
   cin >> A.at(i);
 }
 map<int, int> most;
 for (int x : A)
 {
   if (most.count(x)) // もしすでに含まれているならインクリメント
   {
     most.at(x)++;
   }
   else // 含まれているなら1を追加
   {
     most[x] = 1;
   }
 }
 int max_most = 0; 
 int ans = -1; 
 for (int x : A) // 最頻値の最大値を保持し、その回数をカウント
 {
   if (max_most < most.at(x))
   {
     max_most = most.at(x);
     ans = x;
   }
 }
 cout << ans << " " << max_most << endl;
}

これで提出。

おしまい。