프로그래머스 - 뉴스 클러스터링 - Level 2

문제

풀이전략

1. 입력으로 들어온 문자열을 두 글자씩 잘라서 다중 집합을 만들기
2. 특수문자, 공백, 숫자가 들어오면 그 문자열을 버리기. 즉 매번 2글자씩 자를때마다 확인을 해야함

코드

#include <string>
#include <vector>
using namespace std;

int solution(string str1, string str2) {
    int answer = 0;
    vector<string> A;
    vector<string> B;
    // str1을 2개씩 자른 문자열로 만들어서 A에 넣어주기
    for(int i=0; i<str1.length()-1; i++){
        string tmp = str1.substr(i, 2);
        bool flag = true;
        for(int j=0; j<2; j++){
       	    // 소문자인 부분을 대문자로 바꿔주는 것
            if(tmp[j] >= 97 && tmp[j] <=122){
                tmp[j] = tmp[j] - 32;
            }        
            // 영어가 아닐경우 flag를 false로 바꿔준다.
            else if(!(tmp[j] >= 65 && tmp[j] <90)){
                flag = false;
                break;
            }
        }
        // 영어일경우 A라는 벡터에 넣어준다.
        if(flag){
           A.push_back(tmp); 
        } 
    }
    // str2을 2개씩 자른 문자열로 만들어서 B에 넣어주기
    for(int i=0; i<str2.length()-1; i++){
        string tmp = str2.substr(i, 2);
        bool flag = true;
        for(int j=0; j<2; j++){
            if(tmp[j] >= 97 && tmp[j] <=122){
                tmp[j] = tmp[j] - 32;
            }        
            else if(!(tmp[j] >= 65 && tmp[j] <90)){
                flag = false;
                break;
            }
        }
        
        if(flag){
            B.push_back(tmp); 
        } 
    }
    // 만약 A와 B가 둘다 공집합이라면 65536을 return해준다.
    if(A.size() == 0 && B.size() == 0) return 65536;
    int cnt = 0;
    // 두 문자열을 서로 비교해가며 같은 것의 갯수만 찾는다. 교집합의 갯수
    for(int i=0; i<A.size(); i++){
        for(int j=0; j<B.size(); j++){
            if(A[i] == B[j]){
                cnt++;
                B[j] = " ";
                break;
            } 
        }
    }
    // 합집합은 n(A) + n(B) - n(A 교집합 B) 이므로 이를 이용하여 해결한다. 
    answer = (int)((float)cnt / (float)(A.size() + B.size() - cnt) * 65536);
    // printf("%d %d %d %d\n",'A','Z','a','z');
    return answer;
}

다른분 코드

//string을 소문자로 바꿔주는 스킬이다.
transform(str1.begin(), str1.end(), str1.begin(), ::tolower);
transform(str2.begin(), str2.end(), str2.begin(), ::tolower);

소감

흠.. 문제는 잘 해결하였으나.. 마지막에 두 문자열을 확인하여 교집합을 구할 때 O(n^2)이 되었다. O(n)으로 해결 할 수는 없으려나... 많은 천재분들은 O(n)으로도 해결하셨지만 나는 아직 부족한것 같다. 좀더 노력해야겠다.