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

문제

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

코딩테스트 연습 - [1차] 뉴스 클러스터링

문제풀이

 

문자열을 문자2개로 쪼개는  get_map 함수,

맵 두개를 가지고 교집합 원소 개수를 구하는 get_int 함수,

맵 두개를 가지고 합집합 원소 개수를 구하는 get_union함수, 총 세 함수를 선언하여 풀었다.

 

문자열을 쪼개 map<string, int>에 입력한다. (string은 문자2개, int는 해당 문자열의 개수)

map1과 map2가 있으면 공통 문자열이 있으면 최솟값이 교집합, 최댓값이 합집합에 들어가고, 각각 map의 개수에서 뺀다.

그 다음은 남은 문자열들의 개수를 모두 더하면 합집합의 개수가 된다.

 

void get_map(string str, map<string, int>& m_str) {
    string elem("");
    for (int idx = 1; idx < str.size(); ++idx) {
        if (isalpha(str[idx - 1]) != false && isalpha(str[idx]) != false) {
            elem.clear();
            elem += tolower(str[idx - 1]);
            elem += tolower(str[idx]);

            ++m_str[elem];
        }
    }
}

문자열을 쪼갤때는 대문자, 소문자 구별을 안하므로 isalpha를 이용해 이전 문자와 해당 문자가 알파벳인지 판별을 한다.

알파벳이 아니면 0을 반환하므로 0이 아닐때 elem을 비워주고, 소문자로 변환하여 elem에 더한다.

 

int get_int() {
    int cnt_elem(0), ret(0);
    string elem("");
    for (auto iter1 = m_str1.begin(); iter1 != m_str1.end(); ++iter1) {
        elem = iter1->first;

        cnt_elem = min(m_str1[elem], m_str2[elem]);
        ret += cnt_elem;
        m_str1[elem] -= cnt_elem;
        m_str2[elem] -= cnt_elem;
    }
    return ret;
}

교집합 개수를 구하는 과정이다.

m_str1을 기준으로 탐색하면서 m_str2에도 해당 문자열이 있는지 확인한다.

m_str2[elem]이 0이라면 ret에 더하는 값도 없고 각각 맵에서 뺄 값도 없게 된다.

 

 

int get_union(map<string, int>& m_str) {
    int cnt_elem(0), ret(0);
    string elem("");
    for (auto iter = m_str.begin(); iter != m_str.end(); ++iter) {
        cnt_elem = iter->second;
        ret += cnt_elem;
    }

    return ret;
}

합집합 개수를 구하는 과정이다.

교집합을 구하고 남은 개수를을 모두 ret에 더하고 반환한다.

 

int solution(string str1, string str2) {
    int answer(0), answer1(0), answer2(0);

    get_map(str1, m_str1);
    get_map(str2, m_str2);

    answer1 = get_int();
    answer2 = answer1;

    answer2 += get_union(m_str1);
    answer2 += get_union(m_str2);

    if (answer2 == 0) return 65536;
    answer = (answer1 * 65536) / answer2;

    return answer;
}

메인 문이다.

get_map은 문자열을 쪼개는 함수이므로 각각 실행한다.

 

get_int를 통해 교집합의 개수를 구하고, 교집합 개수를 구하는 변수와 합집합 개수를 구하는 변수에 입력한다.

 

get_union을 통해 남은 문자열들의 개수를 구해 answer2에 더해준다.

 

예제를 보면 분모가 0이면 65536이 정답이므로 따로 조건문을 둔다.

그 외의 경우는 answer1 * 65536 을 answer2로 나눈 몫을 반환한다.

 

코드

#include <string>
#include <vector>
#include <cctype>
#include <algorithm>
#include <map>
using namespace std;

map<string, int>m_str1;
map<string, int>m_str2;

void get_map(string str, map<string, int>& m_str) {
    string elem("");
    for (int idx = 1; idx < str.size(); ++idx) {
        if (isalpha(str[idx - 1]) != false && isalpha(str[idx]) != false) {
            elem.clear();
            elem += tolower(str[idx - 1]);
            elem += tolower(str[idx]);

            ++m_str[elem];
        }
    }
}

int get_int() {
    int cnt_elem(0), ret(0);
    string elem("");
    for (auto iter1 = m_str1.begin(); iter1 != m_str1.end(); ++iter1) {
        elem = iter1->first;

        cnt_elem = min(m_str1[elem], m_str2[elem]);
        ret += cnt_elem;
        m_str1[elem] -= cnt_elem;
        m_str2[elem] -= cnt_elem;
    }
    return ret;
}

int get_union(map<string, int>& m_str) {
    int cnt_elem(0), ret(0);
    string elem("");
    for (auto iter = m_str.begin(); iter != m_str.end(); ++iter) {
        cnt_elem = iter->second;
        ret += cnt_elem;
    }

    return ret;
}

int solution(string str1, string str2) {
    int answer(0), answer1(0), answer2(0);

    get_map(str1, m_str1);
    get_map(str2, m_str2);

    answer1 = get_int();
    answer2 = answer1;

    answer2 += get_union(m_str1);
    answer2 += get_union(m_str2);

    if (answer2 == 0) return 65536;
    answer = (answer1 * 65536) / answer2;

    return answer;
}