ZeroJudge 解題筆記：d574. 節約符咒

作者：王一哲
日期：2025年9月2日


ZeroJudge 題目連結：d574. 節約符咒

解題想法

第4筆測資只有一行，用空格分隔數量與字串，用 Python 解題需要特別處理。依序讀取字串中每個字母，計算連續出現的相同字母數量，將數量與對應的字母組成字串。

Python 程式碼

使用時間約為 1.9 s，記憶體約為 21 MB，通過測試。

line = list(input().split())  # 讀取一行資料並用空格分隔存成串列
n = int(line[0])  # 字串長度
if len(line) == 1: s = input().strip()  # 如果 line 只有一項，再讀取一行字串
else: s = line[1]  # 反之，字串在 line[1]
t = ""  # 儲存答案用的空字串
cnt = 1  # 連續相同字母的數量，預設為 1
last = s[0]  # 前一個字母，預設為 s[0]
for c in s[1:]:  # 依序讀取 s[1] ~ s[n-1]
    if c == last: cnt += 1  # 如果 c 等於 last，cnt 加 1
    else:  # 反之，結算之的連續相同字母數量
        t += str(cnt) + last  # cnt 轉成字串加上 last，接到 t 之後
        cnt = 1  # cnt 重置為 1
        last = c  # last 重置為 c
t += str(cnt) + last  # 最後要再結算一次 cnt 與 last
if len(t) < n: print(t)  # 如果 t 較短，印出 t
else: print(s)  # 反之，印出 s

C++ 程式碼

使用時間約為 0.2 s，記憶體約為 21.2 MB，通過測試。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;  // 字串長度
    string s, t = "";  // 原來的字串，儲存答案用的空字串
    cin >> s;  // 讀取字串
    int cnt = 1;  // 連續相同字母的數量，預設為 1
    char last = s[0];  // 前一個字母，預設為 s[0]
    for(char c : s.substr(1)) {  // 依序讀取 s[1] ~ s[n-1]
        if (c == last) {  // 如果 c 等於 last，cnt 加 1
            cnt++; 
        } else {  // 反之，結算之的連續相同字母數量
            t += to_string(cnt) + last;  // cnt 轉成字串加上 last，接到 t 之後
            cnt = 1;  // cnt 重置為 1
            last = c;  // last 重置為 c
        }
    }
    t += to_string(cnt) + last;  // 最後要再結算一次 cnt 與 last
    if (t.size() < (size_t)n) cout << t << "\n";  // 如果 t 較短，印出 t
    else cout << s << "\n";  // 反之，印出 s
    return 0;
}