[TopCoder, 전체 탐색] 친구 수

1. 내가 짠 코드

import java.util.ArrayList;
import java.util.Arrays;
 
public class test {
    public static void main(String[] args){
        test test = new test();
/*        String[] friends = {"NYNNN",
                            "YNYNN",
                            "NYNYN",
                            "NNYNY",
                            "NNNYN"};*/
        String[] friends = {"NYN",
                            "YNY",
                            "YYN"};
        int answer = test.highestScore(friends);
        System.out.println(answer);
    }
 
    public int highestScore(String[] friends){
        int[] num = new int[friends.length];
 
        for(int i =0 ; i<friends.length;i++){
            ArrayList<Integer> link = new ArrayList<Integer>();
            String temp = friends[i];
            for(int a =0 ; a<friends[i].length();a++){
                if(friends[i].charAt(a)=='Y'){
//                    System.out.println(a);
                    link.add(a);
                }
            }
 
            for(int a =0 ; a < link.size();a++) {
//                System.out.println(link.get(a)+ " = " +friends[link.get(a)]);
                for (int b = 0; b < friends[link.get(a)].length(); b++) {
                    if (b != i && friends[link.get(a)].charAt(b) == 'Y') {
                        friends[i] = friends[i].substring(0, b) + 'Y' + friends[i].substring(b + 1);
                    }
                }
//                System.out.println(friends[i]);
            }
 
            for(int a =0 ; a<friends[i].length();a++){
                if(friends[i].charAt(a)=='Y'){
                    num[i]++;
                }
            }
//            System.out.println(i+"번째 : " + num[i]);
//            System.out.println();
            friends[i] = temp;
        }
 
        Arrays.sort(num);
        return num[num.length-1];
    }
}
 
 
 
 
-----------------------결과------------------------------
2

2. 개선 코드

1. 특정한 사람을 i라고 하면 j사람을 선택해서 직접 친구 여부를 조사합니다.

2. 이때 i와 j가 직접 친구가 아니라면 공통되는 사람 k가 1명이라도 있는지 조사합니다.

3. 위의 조건을 만족하는 j가 있다면 전체 친구의 수를 +1 합니다.

public class test {
    public static void main(String[] args){
        test test = new test();
/*        String[] friends = {"NYNNN",
                            "YNYNN",
                            "NYNYN",
                            "NNYNY",
                            "NNNYN"};*/
        String[] friends = {"NYN",
                            "YNY",
                            "YYN"};
        int answer = test.highestScore(friends);
        System.out.println(answer);
    }
 
    public int highestScore(String[] friends){
        int answer=0;
        int len = friends.length;
 
 
        for(int i =0 ; i<friends.length;i++){
            int cnt = 0;
            for(int a=0; a<len;a++){
                if(i == a) continue;
 
                if(friends[i].charAt(a)=='Y'){
                    cnt++;
                }
                else{
                    for(int k = 0;k<len;k++){
                        if(friends[a].charAt(k)=='Y' && friends[k].charAt(i)=='Y'){
                            //나랑 친구가 아닌 a의 친구중에 내 친구인 k가 있느냐
                            cnt++;
                            break;
                        }
                    }
                }
            }
            answer = Math.max(answer, cnt);
        }
 
        return answer;
    }
}
 
---------------------------결과-------------------------------
2