SRM 436 DIV2 Easy(250) - FriendScore

解くには解けたが、かなり遠回りなコードを書いてしまった。 考えた全探索のロジックは以下の通り。

  1. 探索対象を1人決める(= friends[i])
  2. 探索対象の友達を検索(= friends[i].charAt(j)がYとなる人)
  3. 探索対象の2で抽出した友達以外の友達を検索(= friends[i].charAt(k) ただし、k > j)
  4. 2, 3で抽出された人をそれぞれ友人に設定

Problem Statement

You want to determine the most popular person in a social network. To do this, you will count the number of "2-friends" that each person has. Person A is called a 2-friend of another person B if they are friends with each other or if there exists some person C who is a friend of both A and B. The most popular person is the person with the highest number of 2-friends. (There might be more than one if multiple people all have the maximal number of 2-friends.)

You are given a String friends, where the j-th character of the i-th element is 'Y' if person i and person j are friends, and 'N' otherwise. Return the number of 2-friends of the most popular person in this social network.

Definition

  • Class: FriendScore
  • Method: highestScore
  • Parameters: String
  • Returns: int
  • Method signature: int highestScore(String[] friends) (be sure your method is public)

Limits

  • Time limit (s): 2.000
  • Memory limit (MB): 64

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'.

public class FriendScore {

    public int highestScore(String[] friends) {
        String[] ret = new String[friends.length];
        for (int i = 0; i < friends.length; i++) {
            ret[i] = friends[i];
        }

        for (int i = 0; i < friends.length; i++) {
            for (int j = 0; j < friends[i].length(); j++) {
                if (friends[i].charAt(j) == 'Y') {
                    for(int k = j + 1; k < friends[i].length(); k++) {
                        if (friends[i].charAt(k) == 'Y') {
                            ret[j] = ret[j].substring(0, k) + "Y" + ret[j].substring(k + 1, ret[j].length());
                            ret[k] = ret[k].substring(0,  j) + "Y" + ret[k].substring(j + 1, ret[k].length());
                        }
                    }
                }
            }
        }

        int max = 0;
        for (int i = 0; i < friends.length; i++) {
            int count = 0;
            for (int j = 0; j < friends[i].length(); j++) {
                if (ret[i].charAt(j) == 'Y') {
                    count++;
                }
            }
            max = Math.max(max, count);
        }
        return max;
    }

}