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

프로그래머스의 [1차] 뉴스 클러스터링 (Lv2) 문제이다.

[ 문제풀이 ]

입력으로 주어지는 2개의 문자열을, 2개 단위로 짤라서 저장했을 때, 교집합의 갯수와 합집합의 갯수를 구해야 하는 문제이다.

주어진 문자열들을 어떻게 관리했는지부터 정답을 도출하는 과정까지 다음과 같은 예시를 가지고 진행해보자.

string str1 = "aa1+bc2"

string str2 = "ABcAaa12"

위의 2가지 문자열을 가지고 진행해보자.

#1. 올바른 문자열 추출하기

가장먼저, 주어진 문자열을 앞에서부터 2개씩 짤라서, 올바른 문자열인지 판단해 주었다.

문제에서 제시한대로, 영문자로 된 글자 쌍만 유효하기 때문에, 유효한 문자열이 판단해 주는 것을 가장 먼저 진행해 주었다.

또한, 대소문자 구분이 없다고 했기 때문에, 모두 소문자로 통일해 주었다.

str1과 str2에 대한 올바른 문자열만 적어보면..

str1 = [ "aa" , "bc" ]

str2 = [ "ab" , "bc" , "ca" , "aa", "aa" ]

가 된다.

지금부터는 위와같이, 문제에 조건에 어긋나지 않는, 영문자 글자 쌍으로만 이루어진 문자열들을 "올바른 문자열" 이라고 표현하겠다.

#2. map<string, int> 를 이용한 문자열 관리

간단하게 map에 대해서 알아보자. (map에 대해서 잘 아시는 분들은 #2-1 로 넘어가셔도 좋습니다.)

STL #include<map> 을 선언하면, map이라는 자료구조를 사용할 수 있다.

map은 'key'값이라고 불리는 고유값과, 'value'라고 불리는 해당 고유값이 갖는 값 2개를 쌍으로 관리하는 자료구조이다.

본인이 이 문제에서 선언한 map<string, int> 는, 문자열 'string'을 key값이라고 불리는 고유값으로 사용하고, 해당 string이 가지고 있는 값을 int로 표현하겠다 라고 했는데, 이렇게 선언한 이유는, "해당 문자열이 str1과 str2에 존재하는 갯수를 파악" 하기 위해서이다. 예를 들어서 map<string , int> MAP 이렇게 선언해놓고, MAP["ABC"] = 1 이라고 설정을 하게 되면, 이게 의미하는 것은 "현재 MAP에서 "ABC"라는 key값을 가진 놈이 가지고 있는 값은 '1'입니다." 를 의미한다.

#2-1 map<string, int> 를 이용한 올바른 문자열 갯수 관리

우리가 최종적으로 구해야 하는 값은, str1과 str2에서 발생할 수 있는 올바른 문자열들 중에서, 교집합에 속하는 문자열의 갯수와, 합집합에 속하는 문자열의 갯수를 구해야 한다.

그래서, 본인은 map을 이용해서, str1에서 발생할 수 있는 문자열들의 갯수와 str2에서 발생할 수 있는 문자열들의 갯수를 파악해 주었다.

str1 = { "aa" , "bc" }

str2 = { "ab", "bc", "ca", "aa", "aa" } 가 되는데,

str1의 map에서는 str1_map["aa"] = 1 , str1_map["bc"] = 1이 될 것이고,

str2의 map에서는 str2_map["ab"] = 1 , str2_map["bc"] = 1, str2_map["ca"] = 1 , str2_map["aa"] = 2 가 될 것이다.

위의 숫자들을보면, 각각의 문자열에서 발생할 수 있는 올바른 문자열들과, 그 갯수들을 저장하고 있음을 알 수 있다.

#3. 전체 문자열을 따로 관리

본인은 위에서 이야기했듯이, map으로 2개의 문자열에 대해서, 발생할 수 있는 올바른 문자열들의 갯수를 저장할 뿐 아니라, 발생할 수 있는 모든 문자열들을 중복되지 않게 모두 저장해 주었다.

이 때, vector를 사용해서 관리해 주었는데,

str1 = { "aa" , "bc" }

str2 = { "ab", "bc", "ca", "aa", "aa" } 에 대해서, vector에 저장되는 값들을 확인해보면 먼저 str1에 의해서

[ "aa" , "bc" ] 라는 문자열들이 저장될 것이다.

str2에 의해서는

[ "ab", "ca" ] 가 저장될 것이다. str2에 있는 "aa"와 "ab"가 저장되지 않은 이유는 이미 str1에서 "aa"와 "bc"를 삽입해놓았기 때문에 중복이 되지 않기 삽입하기 위해서 삽입을 하지 않은 것이다.

즉, 결과적으로 vector = { "aa", "bc", "ab", "ca" } 가 된다.

#4. 정답 도출하기

그럼 우리가 지금까지 저장해놓은 값들을 한번 확인해보자.

map_str1["aa"] = 1 , map_str1["bc"] = 1

map_str2["aa"] = 2 , map_str2["bc"] = 1 , map_str2["ab"] = 1 , map_str2["ca"] = 1

vector = { "aa" , "bc" , "ab" , "ca" }

가 된다.

그럼 우리는 지금부터 교집합과 합집합을 구해보자.

만약, str1과 str2에 동일한 올바른 문자열이 있다면, 교집합에서는 더 작은 갯수로 적용되고, 합집합에서는 더 많은 갯수로 적용된다.

따라서, 우리는 전체 문자열들을 탐색하면서, 즉, vector를 순차적으로 탐색하면서 현재 문자열을 str1이 가지고 있는 갯수와 str2가 가지고 있는 갯수를 비교하면서 교집합과 합집합의 갯수를 파악하면 된다.

복잡해보이지만, 말로 설명을 하다 보니 더 복잡해진 것 같다.

소스코드에 주석이 있으니 참고하도록 하자.

[ 소스코드 ]

#include <string>
#include <vector>
#include <map>
 
#define MULTIPLE 65536
using namespace std;
 
 
int Min(int A, int B) { return A < B ? A : B; }
int Max(int A, int B) { return A > B ? A : B; }
 
int Check_State(char C)
{
    if ('A' <= C && C <= 'Z') return 2;
    if ('a' <= C && C <= 'z') return 1;
    return 0;
}
 
char Invert(char C)
{
    C = C - 'A';
    C = C + 'a';
    return C;
}
 
int solution(string str1, string str2) 
{
    vector<string> Total_Str;
    map<string, int> A, B;
 
    /* str1에 대해서 "올바른 문자열" 추출하기. */
    for (int i = 0; i < str1.length() - 1; i++)
    {
        char First = str1[i];
        char Second = str1[i + 1];
        int First_State = Check_State(First);
        int Second_State = Check_State(Second);
        
        if (First_State == 0 || Second_State == 0) continue;
        if (First_State == 2) First = Invert(First);
        if (Second_State == 2) Second = Invert(Second);
        
        string Temp = "";
        Temp = Temp + First;
        Temp = Temp + Second;
        /* 전체 문자열을 관리할 때는, 중복되지 않게 삽입해야한다. */
        /* 중복을 확인하기 위해서는 map에 이미 값이 있는지 확인하면 된다. */
        if (A[Temp] == 0) Total_Str.push_back(Temp);
        A[Temp]++;
    }
 
    /* str2에 대해서 "올바른 문자열" 추출하기. */
    for (int i = 0; i < str2.length() - 1; i++)
    {
        char First = str2[i];
        char Second = str2[i + 1];
        int First_State = Check_State(First);
        int Second_State = Check_State(Second);
 
        if (First_State == 0 || Second_State == 0) continue;
        if (First_State == 2) First = Invert(First);
        if (Second_State == 2) Second = Invert(Second);
 
        string Temp = "";
        Temp = Temp + First;
        Temp = Temp + Second;
        /* str2에서 발생한 문자열도, 전체 문자열을 관리하는 vector에 값을 삽입해야함. */
        /* 물론, 중복이 되지 않게 하기 위해서, map을 이용해서 판단. */
        if (A[Temp] == 0 && B[Temp] == 0) Total_Str.push_back(Temp);
        B[Temp]++;
    }
    
    if (Total_Str.size() == 0) return MULTIPLE;
 
    int Intersection, Union;
    Intersection = Union = 0;
 
    for(int i = 0; i < Total_Str.size(); i++)
    { 
        /* 교집합은, 두 집합 중 더 적은 갯수. */
        /* 합집합은, 두 집합 중 더 큰 갯수. */
        string Str = Total_Str[i];
        Intersection = Intersection + Min(A[Str], B[Str]);
        Union = Union + Max(A[Str], B[Str]);
    }
    
    double answer = (double)Intersection / Union;
    answer = answer * MULTIPLE;
    return (int)answer;
}