[Programmers]#Level2_[1] 뉴스 클러스터링, map 컨테이너

 

#1. 문제

 

프로그래머스

 

---

 

#2. 풀이

 

1. map 컨테이너 

 

[Basic C++] #38_map, 연관 컨테이너

 

map 컨테이너는 C++ 표준라이브러리에서 제공하는 연관 컨테이너로 키와 값을 쌍으로 S저장합니다. map 컨테이너는 레드-블랙 트리(균형 이진트리)로 구현되어 있으며, 데이터 항목의 삽입/삭제 작업 시 내부적으로 정렬 작업을 수행하여 정렬된 상태를 유지하는 특징을 갖고 있습니다. 더불어, map 컨테이너는 Key 값의 중복을 허용하지 않습니다.

 

2. substr(), isalpha(), toupper(), transform()그리고 find()까지!

 

1. 먼저, string1을 두 문자로 substr() 한 뒤, transform()과 toupper()를 활용해 해당 문자들을 Upper-Case로 변환해줍니다.
2. 그리고, 두 문자의 alphabet여부를 isalpha()를 통해 확인하고, unionSet의 총 원소 개수를 +1 증가, 그리고 map 컨테이너 내부 해당 문자들을 키로 하는 값을 +1 증가시켜 줍니다.
3. 다음 string2에 대하여 1~2번을 동일하게 진행해 줍니다. 이때, map 컨테이너에 대하여 find() 알고리즘을 통해 크기가 2로 substr 한 문자열이 이미 존재하는지 확인합니다.
4. 만약, map 컨테이너에 이미 존재하는 문자열일 경우, 해당 키 값에 대하여 값을 -1 감소시켜 주고, jointSeㅅ의 총 원소 개수를 +1 시켜줍니다.
5. 만약, map 컨테이너에 존재하지 않는 문자열일 경우, unionSet의 총 원소 개수에 +1 해줍니다.
6. 마지막으로, unionSet의 총 원소 개수가 0이라면 65536을 출력하고 종료시킵니다. 반대로, unionSet의 총 원소 개수가 0이 아니라면, jointSet / unionSet * 65536 연산의 결과 값을 출력해 줍니다.

 

---

 

#3. 코드

 

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

using namespace std;

int solution(string str1, string str2)
{
    int answer = 0;
    map<string, pair<int, int>> m;
    double unionSet = 0;
    double jointSet = 0;

    for (int i = 0; i < str1.length() - 1; ++i)
    {
        string tmp = str1.substr(i, 2);
        transform(begin(tmp), end(tmp), begin(tmp), ::toupper);
        if (isalpha(tmp[0]) && isalpha(tmp[1]))
        {
            m[tmp].first++;
            unionSet++;
        }
    }

    for (int i = 0; i < str2.length() - 1; ++i)
    {
        string tmp = str2.substr(i, 2);
        transform(begin(tmp), end(tmp), begin(tmp), ::toupper);
        if (isalpha(tmp[0]) && isalpha(tmp[1]))
        {
            auto it = m.find(tmp);
            if (it != end(m) && it->second.first > 0)
            {
                it->second.first--;
                jointSet++;
            }
            else
            {
                unionSet++;
            }
        }
    }

    if (unionSet == 0)
    {
        return 65536;
    }

    answer = (int)((jointSet / unionSet) * 65536);
    return answer;
}

 

---