[Topcoder] InterestingParty(흥미로운 파티)

화이트 씨는 매우 다재다능한 사람이다. 그에게는 모든 것이 확실히 흥미롭다. 아마도 이것이 그에게 많은 친구들이 있는 이유일 것이다.
하지만, 꽤 불행하게도, 그의 친구들 중 누구도 다재다능하지 않다.
그들은 각각 두 가지 주제에만 관심이 있고 다른 어떤 것에 대해서도 말하기를 거부한다.
따라서 화이트 씨가 파티를 조직할 때마다 파티가 모두에게 흥미롭게 보이도록 누구를 초대할지 결정하는 것은 큰 문제입니다.
화이트 씨는 파티를 조직한 경험이 많기 때문에 초대받은 친구들 각자에게 흥미로운 주제가 있을 때만 파티가 흥미로울 것이라는 것을 확실히 알고 있습니다.
당신은 first과 second을 받게 될 것입니다. 화이트 씨의 i번째 친구는 first[i] 와 second[i]주제에 관심이 많다.
화이트 씨가 파티에 초대할 수 있는 가장 많은 수의 친구들을 돌려주세요.

Examples

0)

{"fishing", "gardening", "swimming", "fishing"}

{"hunting", "fishing", "fishing", "biting"}

Returns: 4

This is a very easy case since everybody is interested in "fishing".

1)

{"variety", "diversity", "loquacity", "courtesy"}

{"talking", "speaking", "discussion", "meeting"}

Returns: 1

Despite being interested in "talking", "speaking", "meeting" and so on, these people have nothing to talk about with each other.

2)

{"snakes", "programming", "cobra", "monty"}

{"python", "python", "anaconda", "python"}

Returns: 3

Mr. White can invite friends 0, 1, 3 (0-based) and they will have an interesting evening talking about "python" (or at least Mr. White thinks so).

3)

{"t", "o", "p", "c", "o", "d", "e", "r", "s", "i", "n", "g", "l", "e", "r", "o", "u", "n", "d", "m", "a", "t", "c", "h", "f", "o", "u", "r", "n", "i"}

{"n", "e", "f", "o", "u", "r", "j", "a", "n", "u", "a", "r", "y", "t", "w", "e", "n", "t", "y", "t", "w", "o", "s", "a", "t", "u", "r", "d", "a", "y"}

Returns: 6

---

케이스 0)을 살펴보자.

{"fishing", "gardening", "swimming", "fishing"}

{"hunting", "fishing", "fishing", "biting"}

 

주제 fising이 모든 사람에게 포함되어 있다. 따라서 이들 모두 초대한다. 

 

문제를 푸는 핵심은 가장 많은 사람에게 포함된 주제를 찾고, 이 주제에 흥미있는 사람들의 수를 반환하는 것이다. 

 

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

class InterestingParty{
    public:
    int bestInvitation(vector <string> first, vector <string> second){
        map<string, int> dic;
        
        for(int i=0; i<first.size(); i++){
            dic[first[i]] = 0;
            dic[second[i]] = 0;
        }
        for(int i=0; i<first.size(); i++){
            dic[first[i]]++;
            dic[second[i]]++;
        }
        
        int ans =0;
        map<string, int>::iterator it;
        for(it = dic.begin(); it != dic.end(); it++){
            ans = max(ans, it->second);
        }
        return ans;
    }
};

전체 코드이다. 

        map<string, int> dic;
        
        for(int i=0; i<first.size(); i++){
            dic[first[i]] = 0;
            dic[second[i]] = 0;
        }

주제에 관심있는 인원들을 카운팅하기 위해 <주제 : 인원수> 로 매칭되는 딕셔너리를 선언하고 이를 모두 0으로 초기화한다.

        for(int i=0; i<first.size(); i++){
            dic[first[i]]++;
            dic[second[i]]++;
        }

그리고 각 인원들을 순회하면서 주제별로 인원수를 카운팅한다. 

 

        int ans =0;
        map<string, int>::iterator it;
        for(it = dic.begin(); it != dic.end(); it++){
            ans = max(ans, it->second);
        }
        return ans;

반복자를 사용하여 모든 주제를 순회하여 딕셔너리에서 가장 많은 second(인원수, int)를 반환한다.