# Misty Panther

###### tags: `Easy`
> [name=出題者 : 曾致銘]

## Problem
給定一個整數 `n` ，要求印出一個長度為 `n` 的字串陣列 `answer` 滿足：
- 若 `i` 可被 `3` 和 `5` 整除，則 `answer[i-1] == "MistyPanther"`。
- 若 `i` 可被 `3` 整除，則 `answer[i-1] == "Misty"`。
- 若 `i` 可被 `5` 整除，則 `answer[i-1] == "Panther"`。
- 若不滿足以上條件，則 `answer[i-1] == i`。

### Examples
範例 1：

輸入: 3
輸出: 1 2 Misty

範例 2：

輸入: 5
輸出: 1 2 Misty 4 Panther

範例 3：

輸入: 15
輸出: 1 2 Misty 4 Panther Misty 7 8 Misty Panther 11 Misty 13 14 MistyPanther

### Constraints
- $1 \le$ `n` $\le 10^4$

### Hints

### Extra Challenge
請思考倘若今天題目給定的字串數量非常多時 (如 I Love Misty Panther 8725)，你的演算法是否會看起來很繁雜？有沒有更簡潔的作法？

## Solution
本篇在討論的是如何精進你的演算法，使得在資料增加時，能夠看起來更加簡潔與易讀。

:::spoiler Description
### Approach 1: 直觀算法

#### 思路
你的直覺想法應該是，判斷 `i` 值能否能被 `3`, `5`, 或同時整除。

#### 算法
1. 創建一個長度為 `n` 的字串陣列 `answer` 作為輸出。
2. 遍歷整數 `i` 滿足 $1 \le$ `i` $\le n$。
3. 判斷如果 `i` 可同時被 `3`, `5` 整除，設 `answer[i-1] = "MistyPanther"`。
4. 否則判斷如果 `i` 可被 `3` 整除，設 `answer[i-1] = "Misty"`。
5. 否則判斷如果 `i` 可被 `5` 整除，設 `answer[i-1] = "Panther"`。
6. 否則，設 `answer[i-1] = i`
7. 重複步驟 3 到步驟 6 直至遍歷完成。

// 以下省略 cin, cout，僅呈現演算法部分
// 步驟 1
string answer[n];

for (int i = 1; i <= n; i++) {
    bool divisibleBy3 = (i % 3 == 0);
    bool divisibleBy5 = (i % 5 == 0);
    
    if (divisibleBy3 && divisibleBy5) {
        // 步驟 3
        answer[i - 1] = "MistyPanther";
    } else if (divisibleBy3) {
        // 步驟 4
        answer[i - 1] = "Misty";
    } else if (divisibleBy5) {
        // 步驟 5
        answer[i - 1] = "Panther";
    } else {
        // 步驟 6
        answer[i - 1] = to_string(i);
    }
}

#### 複雜度分析
- 時間複雜度: $O(n)$。
- 空間複雜度: $O(1)$。

### Approach 2: 字串組合

#### 思路
這個算法其實不會減少數學上的計算複雜度，但若資料增加時它能夠更加簡潔。舉例而言，若今天的題目是「Misty Panther 8725」：

3 ---> "Misty", 5 ---> "Panther", 7 ---> "8725"

若你嘗試使用上一種演算法來處理，那麼你將會有很多條件要檢查：

1. 被 3 整除
2. 被 5 整除
3. 被 7 整除
4. 被 3, 5 整除
5. 被 3, 7 整除
6. 被 5, 7 整除
7. 被 3, 5, 7 整除
8. 不被整除

如此一來，當你的資料增加時，你的條件將會指數型成長。因此，與其把每一個數字的組合都判斷一次，不如只判斷個別數字的整除性，並把符合的字串「加」上題目要求的字串，如以 `i == 15` 來舉例：

條件 1: 15 % 3 == 0, answer[14] = "Misty"
條件 2: 15 % 5 == 0, answer[14] += "Panther"
=> answer[14] == "MistyPanther"

在這種情況下，我們只需要判斷 2 次而非上一演算法的 3 次，而對於「Misty Panther 8725」來說，我們也只需要判斷 3 次而非 7 次。

#### 算法

// 以下省略 cin, cout，僅呈現演算法部分
// 作為答案的陣列 「answer」
string answer[n];

for (int i = 1; i <= n; i++) {
    bool divisibleBy3 = (i % 3 == 0);
    bool divisibleBy5 = (i % 5 == 0);
    string numAnsStr = "";
    
    if (divisibleBy3) {
        // 可被 3 整除，字串加上 "Misty"
        numAnsStr += "Misty";
    }
    
    if (divisibleBy5) {
        // 可被 5 整除，字串加上 "Panther"
        numAnsStr += "Panther";
    }
    
    if (numAnsStr == "") {
        // 皆無法被整除，字串加上該數字本身
        numAnsStr += to_string(i);
    }
    
    // 把計算後的結果加入陣列
    answer[i - 1] = numAnsStr;
}

#### 複雜度分析
- 時間複雜度: $O(n)$。
- 空間複雜度: $O(1)$。

### Approach 3: Hash it!

#### 思路
這個算法是上一個算法的再優化。雖然在資料沒有很多時，上個算法感覺已經很好了。但如果今天的題目設計者很邪惡，然後出了一長串的資料怎麼辦？

對於每個數字都寫一個判斷區塊是不可行的，或者說，你的程式最後會有好幾百行然後非常難以閱讀。

再者，倘若今天要改掉其中一個數字，甚至刪除其中一筆資料時，難道我們要把所有區塊都改寫嗎？

其實並不需要。我們可以把資料存在**雜湊表 (Hash Table)** 中。

#### 算法
1. 把所有資料存在一個雜湊表中。如創建 `mistyPantherHash = { 3: "Misty", 5: "Panther" }`。
2. 遍歷整數 `i` 滿足 $1 \le$ `i` $\le n$。
3. 對每個 `i` 遍歷 `mistyPantherHash` 中的每個鍵，判斷其是否可以被整除。
4. 如果步驟 3 成立，那麼把 `mistyPantherHash` 中對應的值加入組合字串中。
5. 把組合字串加入答案陣列。

> 用這種方式你就可以確保，當資料更改時，不需要更改程式內容，只需要更改雜湊表即可。

所以，對於「Misty Panther 8725」來說，它的雜湊表看起來會像是 `{ 3: "Misty", 5: "Panther", 7: "8725" }`

// 以下省略 cin, cout，僅呈現演算法部分
// 答案陣列
string answer[n];

// 雜湊表 mistyPantherDict
unordered_map<int, string> mistyPantherDict = {
    {3, "Misty"}, {5, "Panther"}
};

// 所有除數的陣列
int divisors[] = {3, 5};

for (int i = 1; i <= n; i++) {
    string numAnsStr = "";
    
    for (auto key : divisors) {
        // 若 i 可被 key 整除，就新增對應字串值進 numAnsStr 中
        if (i % key == 0) {
            numAnsStr += mistyPantherDict.at(key);
        }
    }
    
    if (numAnsStr == "") {
        // 皆無法被整除，字串加上該數字本身
        numAnsStr += to_string(i);
    }
    
    // 把計算後的結果加入陣列
    answer[i - 1] = numAnsStr;
}

#### 複雜度分析
- 時間複雜度: $O(n)$。
- 空間複雜度: $O(1)$。

### 完整解答

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

int main() {
    int n;
    cin >> n;
    unordered_map<int, string> mistyPantherDict = {
        {3, "Misty"}, {5, "Panther"}
    };
	
    int divisors[] = {3, 5};

    for (int i = 1; i <= n; i++) {
        string numAnsStr = "";
    
        for (auto key : divisors) {
            if (i % key == 0) {
                numAnsStr += mistyPantherDict.at(key);
            }
        }
    
        if (numAnsStr == "") {
            numAnsStr += to_string(i);
        }

        cout << numAnsStr << " ";
    }

    cout << endl;
}

:::

## Reference
https://leetcode.com/problems/fizz-buzz/