[LeetCode] 1897. Redistribute Characters to Make All Strings Equal

https://leetcode.com/problems/redistribute-characters-to-make-all-strings-equal/description/

Redistribute Characters to Make All Strings Equal - LeetCode

leetcode - Redistribute Characters to Make All Strings Equal

문제 유형 : 해시, 문자열 처리

문제 난이도 : Easy

 

 

문제
You are given an array of strings words (0-indexed).

In one operation, pick two distinct indices i and j, where words[i] is a non-empty string, and move any character from words[i] to any position in words[j].

Return true if you can make every string in words equal using any number of operations, and false otherwise.

 

당신은 문자열 배열 words를 받는다.

한 번의 연산으로, 서로 다른 인덱스 i, j가 있다고 할 때, words[i]에서 words[j]로 한 문자를 떼어서 줄 수 있다.

연산의 수에 제한받지 않고 모든 문자열들을 같은 문자로 만들 수 있을 때, true를, 아니면 false를 반환하시오.

 

 

풀이

문자를 몇 번이고 떼어서 줄 수 있으므로, 우리는 각 문자들의 개수가 모든 문자열들에 동일하게 배분될 수 있는지 찾아야 하고,

배열의 길이 를 n이라고 했을 때, 각 문자들의 개수는 n의 배수여야 한다.

 

map을 이용하여 각 문자들의 빈도를 구한 다음에, 체킹하면 된다.

 

 

코드

C++

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();


class Solution {
public:
    bool makeEqual(vector<string>& words) {
        const int n = words.size();
        unordered_map<char, int> um;

        for(const auto &word:words) {
            for(const auto &ch:word) {
                um[ch]++;
            }
        }

        for(const auto &table : um) {
            if(table.second%n) return false;
        }

        return true;
    }
};