[Algorithm] Programmers :: 뉴스클러스터링

https://school.programmers.co.kr/learn/courses/30/lessons/17677

프로그래머스

 

int solution(string str1, string str2) {
    int answer = 0;
 
    vector<string> v1;
    vector<string> v2;
 
    for (int i = 0; i < str1.size(); i++) 
    {
        str1[i] = toupper(str1[i]);
    }
 
    for (int i = 0; i < str2.size(); i++) 
    {
        str2[i] = toupper(str2[i]);
    }
 
    for (int i = 0; i < str1.size(); i++)
    {
        if (
            (str1[i] >= 65 && str1[i] <= 90) &&
            (str1[i + 1] >= 65 && str1[i + 1] <= 90)
            ) // 둘 다 알파벳이면
        {
            string temp = "";
            temp.append(str1, i, 2);
            v1.push_back(temp);
        }
 
        if (i == str1.size() - 2) break;
    }
 
    for (int i = 0; i < str2.size(); i++)
    {
        if (
            (str2[i] >= 65 && str2[i] <= 90) &&
            (str2[i + 1] >= 65 && str2[i + 1] <= 90)
            ) // 둘 다 알파벳이면
        {
            string temp = "";
            temp.append(str2, i, 2);
            v2.push_back(temp);
        }
 
        if (i == str2.size() - 2) break;
    }
 
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
 
    vector<string>::iterator iter;
 
    // 교집합 구하기
    float count1 = 0;
    vector<string> result1(v1.size() + v2.size());
    iter = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), result1.begin());
 
    for (int i = 0; i < result1.size(); i++)
    {
        if (result1[i] != "") count1++;
    }
 
    // 합집합 구하기
    float count2 = 0;
    vector<string> result2(v1.size() + v2.size());
    iter = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), result2.begin());
 
    for (int i = 0; i < result2.size(); i++)
    {
        if (result2[i] != "") count2++;
    }
 
    if (count2 == 0) return 65536;
 
    float temp = count1 / count2;
    answer = temp * 65536;
 
    return answer;
}

 

카카오 2레벨짜리 문제다. 이 문제의 핵심은 교집합과 합집합을 구하는것이다.

전처리과정 코드가 조금 길긴한데 매우 단순한 코드들이다. str1과 str2를 2개씩 끊어줘서 v1,v2벡터에 넣어주기 위한 과정인데, 나는 헷갈리지 않으려고 그냥 전부 대문자로 바꾼다음 2개씩 끊어서 넣어놨다. 

toupper()함수는 매개변수가 알파벳소문자면 알파벳대문자로 바꿔준다. 그 외의 문자는 그냥 그대로 리턴한다. 그래서 이럴 때 쓰기 편리하다. 

 

algorithm.h에 교집합,합집합을 구할 수 있는 함수들을 지원해주기 때문에 바로 가져다 썼다. 주의할 점은 제대로 값을 얻으려면 정렬을 미리 해놔야 한다는 점이다. 그래서 보면 중간에 v1과 v2 둘 다 sort함수를 이용해 오름차순 정렬을 했다.

그리고 그냥 함수안에 두 벡터의 begin()과 end()를 넣고, 결과물을 리턴받을 vector의 begin()을 넣어주면 끝이다.

교집합과 합집합을 구하는게 관건인데, 둘 다 그냥 쉽게 구해버렸기 때문에 매우 쉽게 풀었다.

이런 함수가 있었다는 걸 알아낸 것 만으로도 굉장히 유익했다. 진짜 실제 코딩테스트때 이런게 있는걸 아는것과 모르는것은.. 시간차이가 굉장히 많이난다.