[알고리즘문제] 릿코드 Find Common Characters

leetcode.com/problems/find-common-characters/submissions/

Find Common Characters - LeetCode

leetCode 

배열 A를 argument로 넘겨준다.

parameter A에는 각 원소마다 문자열들이 들어있고, 각 문자열에 모두 포함되어있는 문자(중복 포함)를 배열로 return하라고 한다.

예시

1

input : ["bella","label","roller"]

output : ["e","l","l"]

각 문자열 별로 e가 하나 l이 2개씩 있으므로 e, l, l return 해야 됨.

 

2.

input : ["cool","lock","cook"]

output : ["c", "o"]

각 문자열 별로 c가 하나 o가 하나 포함 되어있으니 c, o를 return해야 됨.

class Solution {
public:
    vector<string> commonChars(vector<string>& A) {
        vector<string> answer;
        string tmp;
        string tmp2;
        bool _switch;
        for (int i = 0; i < A.size(); i++) {
            tmp = tmp + A[i];
        }

        tmp = delDuplication(tmp);

        for (int i = 0; i < tmp.size(); i++) {
            _switch = false;
            tmp2 = "";
            for (int j = 0; j < A.size(); j++) {
                if (A[j].find(tmp[i]) != string::npos) {
                    _switch = true;
                }
                else {
                    _switch = false;
                    break;
                }
            }
            tmp2 += tmp[i];
            if (_switch) {
                answer.push_back(tmp2);
            }
        }

        map<string, int> re;
        for (int i = 0; i < answer.size(); i++) {
            re.insert(pair<string, int>(answer[i], 0));
        }

        int result = 0;
        for (map<string, int>::iterator it = re.begin(); it != re.end(); it++) {
            _switch = false;
            for (int i = 0; i < A.size(); i++) {
                int count = 0;
                for (int j = 0; j < A[i].size(); j++) {
                    tmp2 = "";
                    tmp2 += A[i][j];
                    if (it->first == tmp2) {
                        count++;
                    }
                }
                if (i == 0) {
                    result = count;
                }
                else {
                    if (result > count) {
                        result = count;
                    }
                }
            }
            it->second = result;
        }

        answer.clear();
        for (map<string, int>::iterator it = re.begin(); it != re.end(); it++) {
            for (int i = 0; i < it->second; i++) {
                answer.push_back(it->first);
            }
        }

        return answer;
    }

    string delDuplication(string &object) {
        vector<char> tmp;
        string re;
        for (int i = 0; i < object.size(); i++) {
            tmp.push_back(object[i]);
        }
        sort(tmp.begin(), tmp.end());
        tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
        for(int i = 0; i < tmp.size(); i++) {
            re = re + tmp[i];
        }
        return re;
    }
};

1. 배열의 모든 원소를 하나의 string에 입력한 후 해당 string의 중복을 제거한다.

2. 해당 string을 이용하여 각 문자열에 모두 포함되어 있는 문자를 기억해 둔다.

3. 각 문자열별로 포함되어있는 문자가 최소 몇개있는지를 기억한다.

 - map을 써서 포함된 문자열을 key로, 문자열의 갯수를 value로 저장한다.

 - map의 정보를 이용하여 문자열을 갯수만큼 배열에 담아서 반환한다.

 

더 좋은방법이 있겠지만 어쩌다보니 코드가 개더러워졌다... ( O(n^3).... )

다행히 submit 후 성공은 했다.