SRM 436 DIV2 Easy(250) - FriendScore
解くには解けたが、かなり遠回りなコードを書いてしまった。 考えた全探索のロジックは以下の通り。
- 探索対象を1人決める(= friends[i])
- 探索対象の友達を検索(= friends[i].charAt(j)がYとなる人)
- 探索対象の2で抽出した友達以外の友達を検索(= friends[i].charAt(k) ただし、k > j)
- 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; } }