(C++, Rust) - LeetCode (easy) 914. X of a Kind in a Deck of Cards

https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/description/

X of a Kind in a Deck of Cards - LeetCode

최대공약수를 이용한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

map을 선언 후 key에는 deck의 원소가, value에는 빈도 수를 저장해줍니다.

📔 풀이과정

1. 1이 a개 2가 b개 3이 c개 있다고 가정해봅니다. 하나의 group은 모두 같은 수로 되어 있어야 하며 각 group의 원소개수는 같아야 하므로 각 원소의 빈도 수들을 나열했을 때 모두 같은 개수의 group으로 나누기 위해서는 이들의 최대공약수가 1보다 큰지 여부를 확인하면 됩니다. 해당값을 구하는 재귀함수 gcd를 uclid 형식으로 구현합니다.

2. 지역변수 g를 선언해 map의 원소를 확인하며 gcd값을 구한 뒤 저장해줍니다.

📔 정답출력

g를 반환합니다.

---

📕 Code

📔 C++

class Solution {
public:
    int gcd(int a, int b) {
        if(!b) return a;
        return gcd(b, a%b);
    }
    bool hasGroupsSizeX(vector<int>& deck) {
        map <int,int> m;
        for(auto d : deck) {
            m[d]++;
        }
        int g = m.begin()->second;
        for(auto el : m) {
            g = gcd(g, el.second);
        }
        return g > 1;
    }
};

📔 Rust

use std::collections::HashMap;

impl Solution {
    pub fn gcd(a: i32, b: i32) -> i32 {
        if b == 0 {
            a
        } else {
            Self::gcd(b, a%b)
        }
    }

    pub fn has_groups_size_x(deck: Vec<i32>) -> bool {
        let mut m = HashMap::new();
        for d in deck {
            let count = m.entry(d).or_insert(0);
            *count += 1;
        }
        let mut g = 1;
        g = *m.iter().next().map(|(_,v)| v).unwrap();

        for &val in m.values() {
            g = Self::gcd(g, val);
        }

        return g > 1;
    }
}

---

📕 Test Case

 몇 가지 반례를 직접 작성해 보았습니다. 

input

[1,1,2,2,2,2]

답

true

 

input

[1]

답

false

 

input

[1,1,1,1,2,2,3,3,3,3,3,3]

답

true

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.