[프로그래머스] [1차] 뉴스 클러스터링 (C++)

풀이

문제의 지문이 엄청 길지만 요약하면 다음과 같다.

두 문자열이 주어지는데, 두 문자열에서 교집합과 합집합을 구한 다음에 교집합 / 합집합의 결과를 65536으로 곱한 값을 리턴하면 된다.

 

하나씩 확인해보자.

1. 문자열에서 영문자로 된 글자 쌍만 유효하며, 아래와 2글자씩 문자열을 쪼개서 넣어놔야 한다.

어떻게 쪼갤 수 있을까?

string의 substr을 이용해서 간단하게 쪼갤 수 있다. 또한 영문자가 아니라면 무시하자.

또 문제에서 보면, "AB" = "Ab" = "ab" 모두 같은 문자로 취급하므로 다 소문자로 만들어서 넣어준다.

vector<string> a;
vector<string> b;
for (int i = 0; i < str1.size() - 1; i++) {
    string s = str1.substr(i, 2);
    if (isalpha(s[0]) && isalpha(s[1])) {
        s[0] = tolower(s[0]);
        s[1] = tolower(s[1]);
        a.push_back(s);
    }
}

for (int i = 0; i < str2.size() - 1; i++) {
    string s = str2.substr(i, 2);
    if (isalpha(s[0]) && isalpha(s[1])) {
        s[0] = tolower(s[0]);
        s[1] = tolower(s[1]);
        b.push_back(s);
    }
}

2. 쪼개는 놨는데, 합집합과 교집합은 어떻게 구할까?

주의할 점이 있는데, 교집합을 구할 때 a의 string과 b의 string이 같다면 단순히 카운트를 하면 안 되고 check 배열을 각각 만들어서 서로 교집합을 체크했다면 true로 체크하면서 중복 여부를 피해 줘야 한다.

int t1 = 0, t2 = 0; // 교집합 수, 합집합 수
vector<bool> a_check(a.size(), false);
vector<bool> b_check(b.size(), false);
for (int i = 0; i < a.size(); i++) {
    for (int j = 0; j < b.size(); j++) {
        if (a[i] == b[j] && !a_check[i] && !b_check[j]) {
            a_check[i] = true;
            b_check[j] = true;
            t1++;
        }
    }
}

합집합은 간단하다. a와 b의 크기를 더한 다음에 교집합의 크기를 빼면 그것이 바로 합집합의 크기다.

t2 = a.size() + b.size() - t1;

만약에 교집합과 합집합이 0이라면 문제에서 바로 65536을 리턴하라고 했으므로 65536을 리턴하고,

아니라면 주어진 공식대로 65536 곱한 다음 소수점을 제외한 값을 리턴하면 된다.

t2 = a.size() + b.size() - t1;
if (a.size() == 0 && b.size() == 0) return 65536;
return (int)((double)t1 / t2 * 65536);

전체 소스 코드는 다음과 같다.

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

int solution(string str1, string str2) {
    vector<string> a;
    vector<string> b;
    for (int i = 0; i < str1.size() - 1; i++) {
        string s = str1.substr(i, 2);
        if (isalpha(s[0]) && isalpha(s[1])) {
            s[0] = tolower(s[0]);
            s[1] = tolower(s[1]);
            a.push_back(s);
        }
    }

    for (int i = 0; i < str2.size() - 1; i++) {
        string s = str2.substr(i, 2);
        if (isalpha(s[0]) && isalpha(s[1])) {
            s[0] = tolower(s[0]);
            s[1] = tolower(s[1]);
            b.push_back(s);
        }
    }

    int t1 = 0, t2 = 0;
    vector<bool> a_check(a.size(), false);
    vector<bool> b_check(b.size(), false);
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b.size(); j++) {
            if (a[i] == b[j] && !a_check[i] && !b_check[j]) {
                a_check[i] = true;
                b_check[j] = true;
                t1++;
            }
        }
    }

    t2 = a.size() + b.size() - t1;
    if (a.size() == 0 && b.size() == 0) return 65536;
    return (int)((double)t1 / t2 * 65536);
}