[프로그래머스] level2 뉴스 클러스터링

나는 문제를 잘못읽어서 2시간 넘게 삽질했다.

 

두 글자씩 끊어서 다중 집합을 만든다. 이때 집합에 특수 기호나 숫자가 들어있을 경우 그 쌍은 버린다.

이 조건을 잘못 읽었다. 어떻게 잘못 읽었냐면

주어진 문자열에서 특수 기호나 숫자를 먼저 모두 지워버리고, 특수 기호나 숫자가 없는 쌍을 만드는 걸로 착각했다.

 

당연히 특수 기호나 숫자를 먼저 지워버리면 제대로된 값이 나오지 않을 것이다. ex) 예제 2, 3번

---

풀이

 

1. 입력 받은 문자열을 모두 대문자로 바꿔준다.
2. 문자열을 2개씩 끊어서 새로운 배열에 넣어준다.
   이때 2개의 문자 중 특수 기호나 숫자가 있으면 배열에 넣지 않고 넘어간다.
3. 배열의 길이는 최대 999 * 999 = 약 100만 이다. 따라서 N^2 풀이가 가능하다고 생각했다.
   2개의 배열을 가지고 2중 for문을 돌면서 2개의 문자열이 같으면 2번째 for문이 관여하는 문자열의 현재 값을 ""으로 바꿔 버렸다.
   교집합에 관여한 문자열을 다시 참조하게 못하게 만들었다.
   그리고 교집합의 개수를 1 증가시킨다.
4. 합집합은 2개의 배열의 크기의 합 - 교집합 이다.

 

 

#include <string>
#include <vector>
#include <map>

using namespace std;

bool validChar(char c){
    if(('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z')){
        return true;
    }
    return false;
}

void strUpper(string &str){
    for(int i = 0; i < str.size(); i++){
        str[i] = toupper(str[i]);
    }
}

void makeVecMap(string &str, vector<string> &vec){
    for(int i = 0; i < str.size()-1; i++){
        string el = "";
        el += str.substr(i, 2);
        if(validChar(el[0]) && validChar(el[1])){
            vec.push_back(el);
        }
    }
}

int solution(string str1, string str2) {
    vector<string> strset1, strset2;
    strUpper(str1);
    strUpper(str2);
    makeVecMap(str1, strset1);
    makeVecMap(str2, strset2);
    
    int inter = 0;
    
    for(int i = 0; i < strset1.size(); i++){
        for(int j = 0; j < strset2.size(); j++){
            if(strset1[i] == strset2[j]){
                inter++;
                strset2[j] = "";
                break;
            }
        }
    }
    
    int sum = strset1.size() + strset2.size() - inter;
    if(sum == 0){
        return 65536;
    }
    double answer = (double)(inter * 65536) / sum;
    
    return (int)answer;
}

 

 

세그먼트 폴트 발생..이었음

프로그래머스 시간 제한 두고 풀다가 이런 에러 나오면 그냥 멘붕..