TopCoder(전체탐색) 즐거운파티

 화이트씨는 다재다능한 사람입니다.(모든 것이 그의 관심 대상입니다.) 그래서 그에게는 친구가 많습니다. 하지만 불행하게도 그의 친구들은 다재다능하지 않습니다. 각각의 친구는 2가지 주제에만 관심이 있고 다른 주제로 이야기하는 것을 싫어합니다.그래서 파티를 개최할 때마다 모두가 즐겁게 파티를 보내려면 어떤 친구를 초대할지가 큰 문제입니다. 화이트씨는 그 동안의 경험으로 초대된 친구 모두가 공통의 흥미 있는 화제가 있을 때 파티를 즐긴다는 것을 알았습니다   문자열 배열 first, second 가 주어집니다.화이트씨의 i번째 친구가 흥미있는 화제는 first[i]와 second[i] 입니다.즐거운 파티가 되려면 화이트씨가 초대할 수 있는 친구는 최대 몇 명인지 리턴하세요.

 

 

[정의 클래스와 함수정의]

public int bestParty(String [] first ,String [] second)  // 저자는 public int bestInvitation(String [] first ,String [] second)

 

문제 풀기 전부터 암울했다 문제를 보면 직감적으로 전체탐색을 머리 속에 떠올려야 한다고 한다 난 이게 전체탐색 이겠구나 했지 전체탐색으로 어떻게 문제를 풀어나가야하는지 전혀 몰랏다 일단 예시를 한번보자

 

[예시: 입력 데이터와 출력 데이터]

 

first = { "fishing" , "gardening"."swimming","fishing"}

secound = {"huting","fishing",fishing","biting"}

return : 4

 

예시를 보면 fishing에 관심이 많다 따라서 공통의 주제가 fishing이고 return값은 4가 나온다

 

그래서 난 열심히 손으로 for문을 1시간반동안 돌려봤다 멍청한건지 끈기가 있는건지 모르겠다.. ㅋㅋ

 

 

 처음에는 공통의 관심사를 가장 많이 있는 단어들을 어떻게 쉽게 찾을수 있을까? 라는 생각을 했다 그래서 처음 단어를 기준으로 first와 second를 조회 하면 되지 않을까? 라는 단서를 얻었고 코드를 작성했지만 실패 했다 그래서 책을 보고 다시 작성하고 손으로 풀어 보니까 이해가됫다 물론 한시간 반이라는 시간이 걸렸지만 말이다.  

 

입력 예시를 보면 첫단어가 fishing 이다 fishing이라는 주제를 하나 잡고 first와 second를 조회하면서 몇번 나왔는지 확인을 하면된다.즉 같은 단어가 나오게 되면 f와 s라는 변수에 카운트를 해주면되는거다 ! 

 

if첫번째 fishing이 걸리고 fishing으로 first[j] ,second[j] 만큼 탐색을해서 공통된 단어가 나온다면 f , s 로 카운트 해주자! 

결과값을 리턴하게 되면 4가 나온다

 

 

 

 

응용 문제를 보자 !

여기는 처음에 HashMap으로 연관검색 방법을 통하여 구하는 방법이다. HashMap은 keySet() 메소드는 모든 키를 Set 객체에 담아서 리턴하는 함수이다.

처음에 first와 second 의 키를 만들어주고 다시 for문을 이용해서 만들어줬던 키값이 나오면 카운트 +1 을 해줘서 벨류값에 1을 더한다

이후 많은 키 값 중 최대값을 빼낸다면 그것이 결과값이 된다.