(LeetCode) 49. Group Anagrams

The link : leetcode.com/problems/group-anagrams/

Group Anagrams - LeetCode

문제는 다음과 같다.

1. C++기준, vector로 문자열이 주어진다.  

2. 애너그램을 통해 같은 쌍의 문자열들을 나열하라. 이때 순서는 상관하지 않는다. 

 

애너그램은 단어의 배열 순서를 바꿔 새로운 단어를 완성하는 암호화인데, 

예를들어 "tea"라는 단어를 새로 나열하여 "eat"만들 수 있다.

 

string으로 된 2차원 vector을 만들었으나, 처음에는 하나의 값을 2차원 vector에 저장하는 법을 몰랐다. 

문득 생각해보니 그냥 {} 중괄호를 넣는 방법을 통해

make_pair로 2개의 값을 저장하지 않아도 하나의 값을 저장할 수 있음을 깨달았다.

 

하지만 처음에는 2중 for문을 통해 하나하나 나열하다가 Time limit이 나왔다.

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        string s1 = "", s2 = "";
        bool ch[10001] = { false, };
        for (int i = 0; i < strs.size(); i++) {
            if (!ch[i]) {
                ch[i] = true;
                ans.push_back({ strs[i] }); // 오 중괄호 넣으니까 되네?
                s1 = strs[i];
                sort(s1.begin(), s1.end());
                for (int j = i + 1; j < strs.size(); j++) {
                    if (!ch[j]) {
                        s2 = strs[j];
                        sort(s2.begin(), s2.end());
                        if (s1 == s2) {
                            ans[ans.size()-1].push_back(strs[j]);
                            ch[j] = true;
                        }
                    }
                }
            }
        }
        return ans;
    }
};

Time limit을 해결하고자 다음과 같은 방법을 진행했다. 

 

1. 문자열 배열 temp를 만든다. 

2. strs의 각 단어들을 오름차순으로 나열하여 temp에 저장한다. 

3. temp의 단어들을 통해 2중 for문으로 비교를 진행한다. 

 

이 방법을 통해 단어 하나하나를 비교할때마다 sort를 하는 번거로움을 줄였다. 

문제는 이렇게 풀고보니 다음과 같은 케이스에서 wrong이 나와버렸다.

언닉불일치 보소...

Run Code에서는 맞았으나 실제로 Submit을 해보니 틀려버리는 이상한 사태가 나와버렸다. 

테스트2번의 input값 [""] 뿐만 아니라 테스트3번의 input값 ["a"]도 마찬가지로 

Run Code에서는 맞았으나 실제 Submit에서는 틀리게 나왔다. 

 

무엇이 틀렸을까 한참을 곰곰히 생각해봤는데, 생각해보니 bool문 배열 ch의 초기화를 안해주었다. 

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<string> temp;
        vector<vector<string>> ans;
        bool ch[10001] = {false,};
        string s1 = "", s2 = "", cnt = "";

        for (int i = 0; i < strs.size(); i++) {
            cnt = strs[i];
            sort(cnt.begin(), cnt.end());
            temp.push_back(cnt);
        }
        for (int i = 0; i < strs.size(); i++) {
            if (!ch[i]) {
                ch[i] = true;
                ans.push_back({ strs[i] }); // 오 중괄호 넣으니까 되네?
                s1 = temp[i];
                for (int j = i + 1; j < strs.size(); j++) {
                    if (!ch[j]) {
                        s2 = temp[j];
                        if (s1 == s2) {
                            ans[ans.size() - 1].push_back(strs[j]);
                            ch[j] = true;
                        }
                    }
                }
            }
        }
        return ans;
    }
};

bool문 ch배열을 초기화 해주니 정답이 나왔다.