FriendScore

문제

문자열 배열 string[] friends 가 주어지고

i번째 사람과 j번째 사람이 친구라면, friends[i][j] 는 'Y' 이다.

( 이때, 친구의 친구도 '친구' 로 본다. )

가장 친구가 많은 사람의 친구 수를 리턴한다.

예시 입력

1)
"NNN",
"NNN",
"NNN"

2)
"NYY",
"YNY",
"YYN"

3)
"NYNNN",
"YNYNN",
"NYNYN",
"NNYNY",
"NNNYN"

4)
"NNNNYNNNNN",
"NNNNYNYYNN",
"NNNYYYNNNN",
"NNYNNNNNNN",
"YYYNNNNNNY",
"NNYNNNNNYN",
"NYNNNNNYNN",
"NYNNNNYNNN",
"NNNNNYNNNN",
"NNNNYNNNNN"

5)
"NNNNNNNNNNNNNNY",
"NNNNNNNNNNNNNNN",
"NNNNNNNYNNNNNNN",
"NNNNNNNYNNNNNNY",
"NNNNNNNNNNNNNNY",
"NNNNNNNNYNNNNNN",
"NNNNNNNNNNNNNNN",
"NNYYNNNNNNNNNNN",
"NNNNNYNNNNNYNNN",
"NNNNNNNNNNNNNNY",
"NNNNNNNNNNNNNNN",
"NNNNNNNNYNNNNNN",
"NNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNN",
"YNNYYNNNNYNNNNN"   

예시 출력

0
2
4
8
6

생각의 변화

친구를 구해두고 친구의 친구를 획득

친구인 사람 구하고 친구 문자열을 OR
이때 자기 자신은 제외

문자열 내에 특정 문자가 어떤 인덱스에 있는지
std::string::find 를 사용한다

친구와, 친구의 친구가 중복되면 안된다
std::set 을 사용

f_index 순회중에 f_index 에 insert 하면 의도하지 않은 동작 위험
copy 해서 사용한다

친구의 친구 중에는 나도 있을수 있다

pseudo code

highestScore(friends)
    res = 0
    self = 0
    
    for f in friends
        set<int> f_index
        start = 0
        
        while (i = f.find('Y', start)) != npos
            f_index.insert(i)
            start = i+1

        set<int> f_index_copy = f_index

        for j in f_index_copy
            start = 0
            
            while (i = friends[j].find('Y', start)) != npos
                if (i != self)
                    f_index.insert(i)
                start = i+1
        
        res = max(res, f_index.size())
        self++

    return res