프로그래머스 - 2018 KAKAO BLIND RECRUITMENT [1차] 뉴스 클러스터링

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

프로그래머스

 

인풋으로 들어온 데이터를 먼저 소문자로 다 변환해줬습니다.

 

그 후, 순서는 없고 개수는 세는 데이터 구조를 만들기 위해서 map을 사용했습니다.

 

데이터를 돌면서 map을 완성하고

 

 

마지막에 합집합과 차지합을 구할 때, C++ map 자료구조의 특성을 이용했습니다. map은 내부적으로 완전 이진트리 형태를 갖추고 있어서 iterator로 차례대로 순회하면 자동으로 정렬된 순서대로 탐색할 수 있습니다.

 

두 데이터 셋의 값을 비교를 통해서 합집합과 차집합을 구하면 되기 때문에, 병합정렬에서 merge 할 때처럼 포인터를 두 개 두어서 병합을 좀 더 빠르게 했습니다. 그래서 전체 시간 복잡도 O(N)으로 풀 수 있었습니다.

 

#include <string>
#include <map>
#include <algorithm>
#include <cctype>
#include <iostream>

using namespace std;

int solution(string str1, string str2) {
    int answer = 0;
    transform(str1.begin(), str1.end(), str1.begin(), ::tolower);
    transform(str2.begin(), str2.end(), str2.begin(), ::tolower);
    
    map<string, int> m1;
    map<string, int> m2;
    map<string, int>::iterator iter1;
    map<string, int>::iterator iter2;
    
    for(int i = 0; i < str1.size() - 1; i++) {
        if(!isalpha(str1[i]) || !isalpha(str1[i + 1])) continue;
        string twoChar = "";
        twoChar += str1[i]; 
        twoChar += str1[i + 1];
        if(m1.find(twoChar) == m1.end()) {
            m1[twoChar] = 1;
        } else {
            m1[twoChar]++;
        }
    }
    
    
    for(int i = 0; i < str2.size() - 1; i++) {
        if(!isalpha(str2[i]) || !isalpha(str2[i + 1])) continue;
        string twoChar = "";
        twoChar += str2[i];
        twoChar += str2[i + 1];
        if(m2.find(twoChar) == m2.end()) {
            m2[twoChar] = 1;
        } else {
            m2[twoChar]++;
        }
    }
    
    // 병합 정렬 합칠 때는 아이디어, 시간 복잡도가 무려 O(1)이다.
    iter1 = m1.begin(), iter2 = m2.begin();
    int sum1 = 0;
    int sum2 = 0;
    while(iter1 != m1.end() && iter2 != m2.end()) {
        if(iter1->first > iter2->first) {
            //합집합으로 가버렷!
            sum2 += iter2->second;
            iter2++;
        } else if(iter1->first < iter2->first) {
            //합집합으로 가버렷!
            sum2 += iter1->second;
            iter1++;
        } else {
            //교집합
            sum1 += min(iter1->second, iter2->second);
            sum2 += max(iter1->second, iter2->second);
            iter1++;
            iter2++;
        }
    }
    
    while(iter1 != m1.end()) {
        //m1에 남은 값들이 m2의 마지막 값보다 더 크다.
        sum2 += iter1->second;
        iter1++;
    }
    
    while(iter2 != m2.end()) {
        sum2 += iter2->second;
        iter2++;
    }
    
    if(sum1 == 0 && sum2 == 0) answer = 65536;
    else {
        answer = ((double)sum1 / (double)sum2) * 65536;
    }
    
    
    return answer;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~