카카오 신입 공채 1차 코딩 테스트 풀이 - 5번문제


작성일 : 2018-06-03 16:55:38
조회수 : 822


본문

5번문제 역시 난이도가 중입니다. 이번 문제에서 조금 주의해야 할 점은 집합에 중복된 원소가 들어가는 것을 허용하는 것입니다. STL 등에서 제공하는 라이브러리 중 multiset, multimap 등 중복을 허용하는 자료구조가 있지만, 사실 저런 원소를 사용할 필요 없이 일반적인 hash, map 등으로 풀 수 있습니다.


원리는 간단합니다. substring 과 int를 가지는 map을 선언하여, 해당 원소의 개수만큼 count를 해줍니다. 그 다음 교집합을 구할 때는 두 집합중 더 적은 갯수의 원소를 가진 쪽의 갯수, 합집합일 때는 더 많은 갯수의 원소를 가진 쪽의 갯수를 취하면 됩니다. 즉


$A=\{1,1,2,2,3\}$ 이고 $B=\{2,3,3,4\}$ 라면, $A[1]=2, B[1]=0, A[2]=2, B[2]=1, A[3]=1, B[3]=2, B[4]=1$ 로 처리를 할 수 있고, 둘중 더 많은쪽과 적은쪽을 각각 교집합과 합집합에 더해주면 됩니다.


문제에서 예외로 발생하는 경우는 공집합일 경우 이를 유사도 1로 규정하라고 되어 있는데, 사실 문제의 정의대로라면 A+B, C*D 도 유사도가 1이 되어버리는 조금 이상한 가정을 하고 있는 것을 알 수 있습니다. 왜 이렇게 했는지는 모르겠지만.. 최종적으로 계산 전 0으로 나뉘는 것을 막기 위해 전처리를 해주면 됩니다.


마지막으로, 문제를 편하게 풀기 위해 모든 문자열을 대문자로 바꾸고 시작합니다.(소문자로 바꿔도 아무상관 없음) 그리고 map의 특성상 존재하지 않는 key를 비교하려고 할 경우 데이터를 집어넣게 되어 비교만으로 불필요한 연산이 늘어날 수 있는 문제가 있습니다. 따라서 밑의 소스에서는 count를 이용해 존재 여부를 체크한 다음 비교하여 불필요한 연산을 최소화 하였습니다.


int solve(string str1, string str2)

{

    transform(str1.begin(), str1.end(), str1.begin(), ::toupper);

    transform(str2.begin(), str2.end(), str2.begin(), ::toupper);


    int a = 0, b = 0;

    

    map<string, int> mp1, mp2;

    for (int i = 0; i < str1.length() - 1; i++)

    {

        string substr1 = str1.substr(i, 2);

        if ('A' <= substr1[0] && substr1[0] <= 'Z'&&'A' <= substr1[1] && substr1[1] <= 'Z')

        {

            mp1[substr1]++;

        }

    }

    for (int i = 0; i < str2.length() - 1; i++)

    {

        string substr2 = str2.substr(i, 2);

        if ('A' <= substr2[0] && substr2[0] <= 'Z'&&'A' <= substr2[1] && substr2[1] <= 'Z')

        {

            mp2[substr2]++;

        }

    }


    for (auto it : mp1)

    {

        if (mp2.count(it.first) > 0)

        {

            a += min(it.second, mp2[it.first]);

            b += max(it.second, mp2[it.first]);

        }

        else

        {

            b += it.second;

        }

    }

    for (auto it : mp2)

    {

        if (mp1.count(it.first) == 0)

        {

            b += it.second;

        }

    }

    if (!a) a = 1;

    a *= 65536;

    if (!b) b = 1;

    return a / b;

}

카카오 신입 공채 1차 코딩 테스트 풀이 - 5번문제 - 알고리즘닷컴
취업 대비 알고리즘에서는 다양한 기업들의 기출 문제 및 경향, 풀이 등에 대한 포스팅을 다룹니다.