문제 푼 날짜 : 2021-07-26

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17677

접근 및 풀이

문제를 제대로 읽지 않아 부분집합을 구할 때 삽질을 많이하다가 시간을 많이 잡아먹었다.
주어진 조건대로만 잘 구현해준다면 쉽게 풀 수 있는 문제였다.

1. 모든 입력을 소문자로 치환해준다.
2. 문자열을 두 개씩 잘라주면서 알파벳일때만 잘라주고, 부분집합을 두 개 만들어준다.
3. 크기가 더 작은 부분집합 원소중에 큰 부분집합에 존재하는 값의 갯수를 세어준다.
4. 두 부분집합의 크기의 합에서 3. 에서 구한 값을 빼준다.

코드

#include <string>
#include <algorithm>

using namespace std;

vector<string> subset(string str) {
    vector<string> sub;
    for (int i = 0; i < str.length() - 1; i++) {
        string tmp = "";
        tmp += str[i];
        tmp += str[i + 1];
        sub.push_back(tmp);
    }
    return sub;
}

int solution(string str1, string str2) {
    double answer = 0;
    if (str1 == "" && str2 == "") {
        return 1 * 65536;
    }
    transform(str1.begin(), str1.end(), str1.begin(), ::tolower);
    transform(str2.begin(), str2.end(), str2.begin(), ::tolower);
    
    vector<string> subset1, subset2;
    for (int i = 0; i < str1.length() - 1; i++) {
        string str = str1.substr(i, 2);
        if (str1[i] >= 'a' && str1[i] <= 'z' && str1[i + 1] >= 'a' && str1[i + 1] <= 'z') {
            subset1.push_back(str);
        }
    }
    for (int i = 0; i < str2.length() - 1; i++) {
        string str = str2.substr(i, 2);
        if (str2[i] >= 'a' && str2[i] <= 'z' && str2[i + 1] >= 'a' && str2[i + 1] <= 'z') {
            subset2.push_back(str);
        }
    }
    
    int unionSize = subset1.size() + subset2.size();
    int intersectSize = 0;
    if (subset1.size() < subset2.size()) {
        for (auto a : subset1) {
            auto iter = find(subset2.begin(), subset2.end(), a);
            if (iter != subset2.end()) {
                intersectSize++;
                subset2.erase(iter);
            }
        }
    } else {
        for (auto a : subset2) {
            auto iter = find(subset1.begin(), subset1.end(), a);
            if (iter != subset1.end()) {
                intersectSize++;
                subset1.erase(iter);
            }
        }
    }
    unionSize -= intersectSize;
    
    if (unionSize == 0) {
        return 65536;
    }
    
    answer = (double) intersectSize / unionSize;
    return answer * 65536;
}

결과

피드백

문제를 꼼꼼히 읽고, 알고리즘을 좀 더 신중히 생각하는 연습을 하자.