a291: nAnB problem

這篇教學會示範 ZeroJudge 基礎題庫「a291: nAnB problem」的解題過程。

題目需求

題目會先提供一組正確的四位數字密碼，接著會有數組猜密碼的數字，對於每組嘗試的密碼，若有 p 個數字的值正確且在正確的位子上，輸出 pA，另外有 q 個數字的值正確，但不在正確的位子上，輸出 qB，將 AB 組合為 pAqB 輸出。

題目連結：a291: nAnB problem

解答

這題看似很像猜數字幾 A 幾 B，但實際運作卻不太相同，這題的關鍵有兩個，第一個關鍵必須使用 stdin，因為測驗的資料量很大，使用 input 會發生 TLE 超時的狀況，第二個關鍵是在比對數字位置正確的到 A 之後，要將該數字刪除，避免重複比對造成 B 的結果錯誤。

參考：字典生成式、複製字典、複製串列、for 迴圈

from sys import stdin
output = ''         # 建立 output，最後再一次輸出 ( 不用每次執行都輸出 )
for s in stdin:     # 讀取逐行輸入
  if s.strip() == '': continue  # 如果遇到換行，就跳過
  pwd = s.split()    # 將正確的密碼變成串列
  dic = {str(k):0 for k in range(10)}   # 建立一個 key 為 0～9 的字典檔 dic
  for i in pwd: dic[i] += 1     # 使用字典檔 dic 記錄密碼中數字出現幾次
  n = int(stdin.readline())     # 再來會出現幾次嘗試的密碼
  for _ in range(n):            # 重複嘗試的次數
    ans = stdin.readline().split()    # 將嘗試的解答拆成串列
    a, b, c, d = 0, 0, pwd[:], dic.copy()
    # 建立四個變數，分別是答案 ab，複製密碼串列的 c，複製 dic 的 d
    # 由於每次判斷都會修改，為了避免修改到原始資料，複製一份出來使用
    for j in range(4):
      if ans[j] == pwd[j]:     # 如果包含數字且位置正確
        d[str(pwd[j])] -= 1    # 將字典對應 key 的數值減少 1
        a = a + 1              # a 增加 1
        c[j] = 'o1'            # 修改複製的密碼位置為 o1
        ans[j] = 'o2'          # 修改嘗試的密碼位置為 o2 ( 下次就不會比對這個 )
    for j in ans:
      if j in c and d[j]>0:    # 如果有包含且字典檔 key 的值還大於 0 ( 表示還沒有被比對 )
        d[j] -= 1              # 字典檔數值減少 1
        b = b + 1              # b 增加 1
    output = output + f'{a}A{b}B\n'   # 將結果記錄到輸出的 output
print(output)   # 全部完成後一併輸出

意見回饋

如果有任何建議或問題，可傳送「意見表單」給我，謝謝～