2. 전체 탐색(즐거운 파티)

전체탐색:

-선택 사항이 몇개 있고 어떤 것을 선택해야 할지 모른다면 모든 경우를 테스트하자는 것

-모든 패턴을 조사해야 하는 것과 그것을 필요로 하는문제

-시뮬레이션과 다르게 어떠한 작업을 수행할지 적혀있지 않음 

문제(즐거운 파티)

화이트씨는 다재다능한 사람입니다.(모든 것이 그의 관심 대상입니다). 그래서 그에게는 친구가 많습니다.
하지만 불행하게도 그의 친구들은 다재다능하지 않습니다. 각각의 친구는 2가지 주제에만 관심이 있고
다른 주제로 이야기 하는 것을 싫어합니다. 그래서 파티를 개최할 때마다 모두가 즐겁게 파티를 보내려면
어떤 친구를 초대할지가 큰 문제입니다. 화이트씨는 그동안의 경험으로 초대된 친구 모두가 공통의 흥미 있는
화제가 있을 때 파티를 즐긴다는 것을 알았습니다.

문자열 배열 first, second가 주어집니다. 화이트씨의 i번째 친구가 흥미있는 화제는 first[i]와
second[i]입니다. 즐거운 파티가 되려면 화이트씨가 초대할 수 있는 친구는 최대 몇 명 인지 리턴하세요.

입력

first : 1~50개의 요소가 있는 배열.
second : 1~50개의 요소가 있는 배열.
first, second 공통 : 각 요소는 1~15개 문자이며, 각 문자는 영어 소문자입니다.
i번째 요소 first[i]와 second[i]의 내용은 다릅니다.

출력

정수를 담고있는 변수

IO Example

# Case# 0
first = ['fishing', 'gradening', 'swimming', 'fishing']
second = ['hunting', 'fishing', 'fishing', 'biting']
result = 4
 
# Case# 1
first = ['Variety', 'diversity', 'loquacity', 'courtesy']
second = ['talking', 'speaking', 'discussion', 'meeting']
result = 1
 
# Case# 2
first = ['snakes', 'programming', 'cobra', 'monty']
second = ['python', 'python', 'anaconda', 'python']
result = 3
 
# Case# 3
first = ['t', 'o', 'p', 'c', 'o', 'd', 'e', 'r', 's', 'i', 'n', 'g', 'l', 'e',
 'r', 'o', 'u', 'n', 'd', 'm', 'a', 't', 'c', 'h', 'f', 'o', 'u', 'r', 'n', 'i']
second = ['n', 'e', 'f', 'o', 'u', 'r', 'j', 'a', 'n', 'u', 'a', 'r', 'y', 't',
 'w', 'e', 'n', 't', 'y', 't', 'w', 'o', 's', 'a', 't', 'u', 'r', 'd', 'a', 'y']
result = 6

구현

1차 코드 :  반복문과 조건문을 활용해 max값을 갱신해갔다.

 public class bestInvitation1 {
    public static void main(String[] args) {
        
        String[] first=new String[]{"1","2","3","3","3","3"};
        String[] second=new String[]{"2","3","5","6","7","8"};
        
        System.out.println(bestInvitation(first,second));
        
}
    private static int bestInvitation(String[] first, String[] second) {
        int max=0;
        int temp=0;
        
        for(int i=0; i<first.length; i++) {
            for(int k=0; k<first.length; k++){
                if(first[i].equals(first[k]) || first[i].equals(second[k]) ) {
                    temp++;
                    if(temp > max)
                        max=temp;
                }
            }
            temp=0;
        }
        
        for(int i=0; i<second.length; i++) {
            for(int k=0; k<second.length; k++){
                if(second[i].equals(second[k]) || second[i].equals(first[k]) ) {
                    temp++;
                    if(temp > max)
                        max=temp;
                }
            }
            temp=0;
        }
        return max;
    }
}

2차 코드 : 좀더 가독성을 살리고 효율적으로 정리하였다.

private static int bestInvitation(String[] first, String[] second) {
        int ans=0;
        int f;
        int s;
        
        for(int i=0; i<first.length; i++) {
            f=0;
            s=0;
            for(int j=0; j<first.length; j++) {
                if(first[i].equals(first[j]) || first[i].equals(second[j]) ) {
                    f++;
                }
                if(second[i].equals(first[j]) || second[i].equals(second[j]) ) {
                    s++;
                }
            }
            ans = Math.max(f,ans);
            ans = Math.max(s,ans);
        }
        return ans;
    }

3차 코드 : 해시맵을 활용하여 각 키에 해당하는 값을 갱신하고 max값을 구하였다.

private static int bestInvitation(String[] first, String[] second) {
        int ans=0;
        
        HashMap<String,Integer> map = new HashMap<String,Integer>();
        
        for(int i=0; i<first.length; i++) {
            if(map.containsKey(first[i])) {
                map.put(first[i], map.get(first[i])+1);
            }else {
                map.put(first[i],1);
            }
            if(map.containsKey(second[i])) {
                map.put(second[i], map.get(second[i])+1 );
            }else {
                map.put(second[i],1);
            }
        }
        
        for(String key : map.keySet()) {
            ans = Math.max(ans, map.get(key));
        }
        
        return ans;
    }

4차 코드 : 해시맵을 다시 활용 좀더 단순화 시켰다.

private static int bestInvitation(String[] first, String[] second) {
        int ans=0;
        
        HashMap<String,Integer> map = new HashMap<String,Integer>();
        
        for(int i=0; i<first.length; i++) {
            map.put(first[i],0);    
            map.put(second[i],0);    
        }
        for(int i=0; i<first.length; i++) {
            map.put(first[i],map.get(first[i])+1);    
            map.put(second[i],map.get(second[i])+1);    
        }
            
        for(String key : map.keySet()) {
            ans = Math.max(ans, map.get(key));
        }
        return ans;
    }