ZeroJudge 解題筆記：g006. 密碼備忘錄 (Password)

作者：王一哲
日期：2025年3月23日



ZeroJudge 題目連結：g006. 密碼備忘錄 (Password)

解題想法

這題我用字典計數，再用 cmp_to_key 或 lambda function 自訂比較式。

Python 程式碼

使用時間約為 24 ms，記憶體約為 3.9 MB，通過測試。

import sys
from collections import Counter
from functools import cmp_to_key

def mycmp(a, b):  # (key, val)
    if a[1] > b[1]: return -1  # 如果 a[1] > b[1]，a 往前放
    elif a[1] < b[1]: return 1  # 如果 a[1] < b[1]，a 往後放
    else:  # 如果 a[1] == b[1]
        if a[0] < b[0]: return -1  # 如果 a[0] < b[0]，a 往前放
        elif a[0] > b[0]: return 1  # 如果 a[0] > b[0]，a 往後放
        else: return 0

for s in sys.stdin:
    cnt = Counter(s.strip())  # 刪除 s 結尾的 \n，用 Counter 計算各字母數量
    ans = sorted([(k, v) for k, v in cnt.items()], key=cmp_to_key(mycmp))  # 排序
    print("".join([k for k, v in ans]))  # 將 k 取出組成字串再印出

C++ 程式碼

使用時間約為 2 ms，記憶體約為 352 kB，通過測試。

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s;  // 輸入的字串
    while(cin >> s) {
        map<char, int> cnt;  // 計算各字母數量
        for(char c : s) cnt[c]++;
        vector<pair<char, int>> ans;  // 取出 cnt 的 (key, val) 放入 ans
        for(auto it : cnt) ans.push_back(it);
        sort(ans.begin(), ans.end(), [] (pair<char, int> a, pair<char, int> b) {
            if (a.second == b.second) return a.first < b.first;
            else return a.second > b.second; } );   // 排序
        for(int i=0; i<(int)ans.size(); i++) {  // 印出 ans.first
            cout << ans[i].first << (i == (int)ans.size()-1 ? "\n" : "");
        }
    }
    return 0;
}