[TopCoder] 초급 - 전체 탐색

 이전에 시뮬레이션은 간단하게 주어진 문제를 간단히 구현만 하면 되는 문제였습니다.

이번에는 가장 좋은 결과를 얻는 것에 관한 문제입니다. 

그 중 대표적인 것이 바로 전체 탐색입니다. 

  문제

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

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

  해석

first={ fishing, gardening, swimming, fishing }

second ={ hunting, fishing, fishing, biting }

결과값 : 4

같은 흥미있는 주제를 가진 사람 중에 최대로 파티를 즐길 수 있는 사람의 수를 구하는 문제입니다. 그렇기 때문에 fishing 흥미를 가지고 있는 사람은 총 4명으로 최대입니다.

  코드

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

저는 for문을 벗어날수가 없어서.. 일단 이렇게 작성은 했지만 책에는 map을 사용해 간단하게 구현을 했습니다.

모든 if문을 제거하고 map의 특성을 이용하여 간단하게 작성했습니다. 참 어떻게 이런 생각을 하지는 신기할 따름입니다.

아직 저는 배울 것이 너무 많다고 또 한번 느끼네요