# 0-21 map

講義不是我寫的，網址在此 https://emanlaicepsa.github.io/2020/10/21/0-index/
我只是將自己寫的練習題程式碼記錄下來。
最後更新日期：2024年10月9日

## [TOJ: 55](https://toj.tfcis.org/oj/pro/55/)

本題在〈[0-14 常用工具/函式](https://hackmd.io/@yizhewang/ByFcXglJ1g)〉中有出現過，當時是用 Python 的 bisect 函式庫及 C++ 的 algorithm 函式庫工具解題。

### Python 程式碼

用 collections 函式庫的 Counter 計數，但是第3筆測資記憶體爆掉。

from collections import Counter

n = int(input())
songs = list(map(int, input().split()))
cnt = Counter(songs)
m = int(input())
for _ in range(m):
    print(cnt[int(input())])

### C++ 程式碼

用 map 字典計數，執行時間最久約為 1697 ms，使用記憶體最多約為 48944 kB，通過測試。

#include <iostream>
#include <map>
using namespace std;

int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    int N, M, song; cin >> N;
    map<int, int> songs;
    for(int i=0; i<N; i++) {
        cin >> song;
        songs[song]++;
    }
    cin >> M;
    for(int i=0; i<M; i++) {
        cin >> song;
        cout << songs[song] << "\n";
    }
    return 0;
}

用 unordered_map 字典計數會更快，執行時間最久約為 784 ms，使用記憶體最多約為 40604 kB，通過測試。

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    int N, M, song; cin >> N;
    unordered_map<int, int> songs;
    for(int i=0; i<N; i++) {
        cin >> song;
        songs[song]++;
    }
    cin >> M;
    for(int i=0; i<M; i++) {
        cin >> song;
        cout << songs[song] << "\n";
    }
    return 0;
}

## [ZeroJudge: d518. 文字抄寫 II](https://zerojudge.tw/ShowProblem?problemid=d518)

### Python 程式碼

執行時間最久約為 2.2 s，使用記憶體最多約為 3.5 MB，通過測試。

import sys

for line in sys.stdin:
    N = int(line)
    words = {}
    i = 1
    for _ in range(N):
        word = input()
        if word not in words:
            words[word] = i
            print("New! {:d}".format(words[word]))
            i += 1
        else:
            print("Old! {:d}".format(words[word]))

### C++ 程式碼

執行時間最久約為 0.5 s，使用記憶體最多約為 1.2 MB，通過測試。

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    int N;
    while(cin >> N) {
        string word;
        map<string, int> words;
        int idx = 1;
        for(int i=0; i<N; i++) {
            cin >> word;
            auto it = words.find(word);
            if (it == words.end()) {
                words.emplace(word, idx);
                cout << "New! " << words[word] << "\n";
                idx++;
            } else {
                cout << "Old! " << words[word] << "\n";
            }
        }
    }
    return 0;
}

改用 unordered_map 會比較快，執行時間最久約為 0.3 s，使用記憶體最多約為 2.1 MB，通過測試。

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    int N;
    while(cin >> N) {
        string word;
        unordered_map<string, int> words;
        int idx = 1;
        for(int i=0; i<N; i++) {
            cin >> word;
            auto it = words.find(word);
            if (it == words.end()) {
                words.emplace(word, idx);
                cout << "New! " << words[word] << "\n";
                idx++;
            } else {
                cout << "Old! " << words[word] << "\n";
            }
        }
    }
    return 0;
}

------

###### tags:`演算法`、`APCS`、`Python`、`C++`