[Topcoder] Freindscore(친구 점수)

소셜 네트워크에서 가장 인기 있는 사람을 결정하려고 합니다. 이렇게 하기 위해, 여러분은 각각의 사람들이 가지고 있는 "2-친구"의 수를 셀 것입니다. 사람 A는 서로 친구이거나 A와 B의 친구인 사람 C가 존재하는 경우 다른 사람 B의 2-친구라고 불린다. 가장 인기 있는 사람은 2-친구가 가장 많은 사람입니다. (여러 명이 2- 친구가 가장 많은 경우에는 둘 이상일 수 있습니다.)
친구가 주어지는데, i번째 요소의 j번째 문자는 인칭 i와 인칭 j가 친구이면 'Y'이고, 그렇지 않으면 'N'이다.
이 소셜 네트워크에서 가장 인기 있는 사람의 친구 2명의 번호를 반환합니다.

Definition

Class:

 

FriendScore

Method:

 

highestScore

Parameters:

 

tuple (string)

Returns:

 

integer

Method signature:

 

def highestScore(self, friends):

Constraints

- friends will contain between 1 and 50 elements, inclusive.

- Each element of friends will contain exactly N characters 'Y' or 'N', where N is the number of elements in friends.

- For each i and j, friends[i][j] will be equal to friends[j][i].

- For each i, friends[i][i] will be equal to 'N'.

Examples

0)

{"NNN", "NNN", "NNN"}

Returns: 0

Here, there are 3 people and none of them are friends, so everybody has zero 2-friends.

1)

{"NYY", "YNY", "YYN"}

Returns: 2

Each person has two 2-friends.

2)

{"NYNNN",

 "YNYNN",

 "NYNYN",

 "NNYNY",

 "NNNYN"}

Returns: 4

Persons 0 and 4 have two 2-friends, persons 1 and 3 have three 2-friends. Person 2 is the most popular one - four 2-friends.

3)

{"NNNNYNNNNN",

 "NNNNYNYYNN",

 "NNNYYYNNNN",

 "NNYNNNNNNN",

 "YYYNNNNNNY",

 "NNYNNNNNYN",

 "NYNNNNNYNN",

 "NYNNNNYNNN",

 "NNNNNYNNNN",

 "NNNNYNNNNN"}

Returns: 8

4)

{"NNNNNNNNNNNNNNY","NNNNNNNNNNNNNNN", "NNNNNNNYNNNNNNN", "NNNNNNNYNNNNNNY", "NNNNNNNNNNNNNNY", "NNNNNNNNYNNNNNN", "NNNNNNNNNNNNNNN", "NNYYNNNNNNNNNNN", "NNNNNYNNNNNYNNN", "NNNNNNNNNNNNNNY", "NNNNNNNNNNNNNNN", "NNNNNNNNYNNNNNN", "NNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNN", "YNNYYNNNNYNNNNN"}

Returns: 6

 

 

---

소셜 네트워크가 Y과 N으로 이루어진 행렬로 주어졌을 때, 

 

가장 친구가 많은 경우의 친구 수를 반환하는 문제이다. 주목할 점은 A와 B가 친구, B와 C가 친구일 때 

 

A와 C도 친구로 간주하는 조건이다. 

 

3)의 케이스를 살펴보자. 

0{"NNNNYNNNNN",

1 "NNNNYNYYNN",

2 "NNNYYYNNNN",

3 "NNYNNNNNNN",

4 "YYYNNNNNNY",

5 "NNYNNNNNYN",

6 "NYNNNNNYNN",

7 "NYNNNNYNNN",

8 "NNNNNYNNNN",

9 "NNNNYNNNNN"}

사람 0의 경우 "NNNNYNNNNN" 사람 4이랑만 친구이다.

 

사람 4의 경우를 살펴보자. 4 "YYYNNNNNNY",

 

사람0 이외에도 사람1, 2, 9와 친구이다. 이 사람들이 사람 0의 친구로도 간주된다. 

 

따라서 사람 0의 전체 친구 수는 총 4명이다. 

 

행렬의 행을 순차적으로 탐색하면서 각 사람의 친구수를 위 방식으로 구한 뒤, 가장 max 값을 반환한다. 

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

class FriendScore{
    public:
    int highestScore(vector <string> friends){
        int ans=0;
        int man_num = friends[0].length();
        for(int i=0; i<man_num; i++){
            int cnt = 0;
            for(int i_fr=0; i_fr<man_num; i_fr++){
                if(friends[i][i_fr]=='Y'){
                    cnt++;
                    for(int i_fr_fr=0; i_fr_fr<man_num; i_fr_fr++){
                        if(friends[i_fr][i_fr_fr] == 'Y' && i_fr_fr!=i && friends[i][i_fr_fr] == 'N'){
                            cnt++;
                        }
                    }
                }
            }
            ans = max(ans, cnt);
        }
        return ans;
    }
};

전체 코드이다. 

 

        int man_num = friends[0].length();

소셜 네트워크를 구성하는 전체 인원수를 구한다. 

for(int i=0; i<man_num; i++){

각 행을 순회하면서 친구수를 구한다. 

            for(int i_fr=0; i_fr<man_num; i_fr++){
                if(friends[i][i_fr]=='Y'){
                    cnt++;

사람 X(i)에 대해서 열(i_fr)을 순회하면서 친구라고 되어있으면(Y) 친구수를 카운팅한다. 

 for(int i_fr_fr=0; i_fr_fr<man_num; i_fr_fr++){
	if(friends[i_fr][i_fr_fr] == 'Y' && i_fr_fr!=i && friends[i][i_fr_fr] == 'N'){
	cnt++;
}

그리고 바로 그 친구(i_fr)의 행으로 넘어가서

 

친구의 친구까지 내 친구로 포함한다. (friends[i_fr][i_fr_fr] == 'Y')

 

i_fr_fr!=i && friends[i][i_fr_fr] == 'N'

 

다만 이중 카운팅을 방지하기 위해 이 친구의 친구가 '나'이거나, 이미 내 친구이면 카운팅하지 않는다.

 

            ans = max(ans, cnt);
        }
        return ans;

 

max 값을 갱신하고, 전체 for문을 돈 이후에 이 max 값(가장 많은 친구수)을 반환한다.