23.04.28. 풀었던 문제들

Leetcode 839. Similar String Groups

 n이 작다는 점에서 2중for문을 고려할 만한 문제. DFS와 같은 방식으로, [어떤 string과 유사한 string]을 찾으면 계속 이어 나가서 하나의 group을 만들어야 한다. 단순 DFS로만 구현해도 되긴 하다.

 DFS로 구현하면

• 어떤 string을 탐색할 때 모든 strs를 탐색하며 유사한 것을 찾고, 찾는다면 그것으로 DFS를 한다.
• 찾은 것은 따로 넘버링을 하고 넘버링의 개수를 리턴한다.

 

 나는 union-find로 구현했다. union-find 특성상 dfs보다 좀 더 빠르고 메모리도 적게 사용할 것이라 생각했기 때문. Union-find는 내가 작성했던 포스트와 동일하게 구현했다.

 그러면 이 문제의 메인 로직.

• 2중 for문을 돌면서 두 string이 similar라면 union한다.
• union 결과로 root의 개수를 센다.
• similar 판정은, 두 string 비교하며 철자가 다른 부분이 2곳 이하이면 similar한 것이다.
  • 0곳이면 같은 경우, 1곳인 경우는 존재하지 않으며 2곳인 경우는 문제가 정의한 simliar이다.

// Runtime 173 ms Beats 48.57%
// Memory 10.6 MB Beats 49.21%

class Solution {
public:
    vector<int> parents;
    vector<int> ranks;
    int sz;
    void makeDS(int size){
        parents.resize(size);
        for(int i = 0; i<size; i++) parents[i] = i;
        ranks.resize(size, 0);
    }

    int find(int v){
        if(v == parents[v]) return v;
        parents[v] = find(parents[v]);
        return parents[v];
    }

    void join(int x, int y){
        int rx = find(x), ry = find(y);
        if(ranks[rx] > ranks[ry]){ // ry가 rx 아래에 들어감
            parents[ry] = rx;
        }
        else{
            if(ranks[rx] == ranks[ry]){
                ranks[ry]++;
            }
            parents[rx] = ry;
        }
    }

    int numSimilarGroups(vector<string>& strs) {
        int len = strs.size();
        makeDS(len); // *** 실수 : disjoint set 초기화를 하지 않았음.

        for(int i = 0; i<len; i++){
            for(int j = i+1; j<len; j++){
                if(isSimilar(strs[i], strs[j])){
                    join(i, j);
                }
            }
        }

        set<int> answer;
        for(int i = 0; i<len; i++){ // *** 실수 : find(i)를 결과에 넣어야 하는데 parents[i]를 넣음.
            answer.insert(find(i));
        }
        return answer.size();
    }

    bool isSimilar(string &s1, string &s2){
        int diffCnt = 0, len = s1.length();
        for(int i = 0; i<len; i++){
            if(s1[i] != s2[i]) diffCnt++;
        }
        return diffCnt <= 2;
    }
};

 

시간복잡도

 strs.size()를 n, strs[0].length()를 m이라 했을 때,

 isSimilar 함수는 string length만큼 순회하므로 O(m), union에 O(log*n)이다. 

 main 함수는 2중 for문으로 $n^2$을 돌고, 모든 for문에서 각 string의 비교를 하는 isSimilar 함수를 호출하기에 O($n^{2}(m+log*n)$)이다.

 

공간복잡도

 parents, ranks vector를 사용하므로 O(n)

 

후기

빡세당