[TopCoder 알고리즘] 전체탐색 - 즐거운 파티

시뮬레이션 문제에서 주어진 과정을 거쳐 나온 결과가 무엇인지 묻는다면, 전체 탐색 유형은 과정을 알려주지 않고 "가장 좋은 결과는 무엇인지" 등을 물어볼 수 있다.

선택 사항이 몇 개가 있고 어떤 것을 선택해야 할지 모르는 상황에서 전체 탐색은 모든 경우를 테스트하는 전략이다.

 

---

Problem : Interesting Party

 

화이트씨는 다재다능한 사람이다. 그래서 그는 친구가 많다. 하지만 불행히도 그의 친구들은 누구도 다재다능하지 않다. 그들은 각자 두 개의 관심사만을 가지고 있고, 그 이외의 주제에 대해서는 대화하고 싶어 하지 않는다. 따라서 화이트 씨는 파티를 주최할 때, 모두에게 파티가 흥미롭기 위해서는 누구를 초대해야 하는지 고민이다. 화이트 씨는 파티 경험이 많지는 않지만, 친구들 모두가 공통으로 관심 있는 주제가 있을 때만 즐거운 파티가 될 것임을 알고 있다. 문자열 배열 first와 second가 주어진다. 화이트씨의 i번째 친구는 first[i]와 second[i] 주제에 관심이 있다. 즐거운 파티가 되려면 화이트 씨가 초대할 수 있는 친구는 최대 몇 명인지 리턴하라.

 

 

제약 조건 :

 

first : 1-50개의 요소를 갖는 배열second : first와 같은 크기의 배열 first, second 공통 - 각 요소는 1-15개의 문자이며, 각 문자는 영어 소문자이다. first[i]와 second[i]의 내용은 다르다

 

 

예시 :

 

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

second = {"hunting" , "fishing" , "fishing" , "biting"}

 

Returns : 4

 

---

문제 해설

 

"가장 많은 것을 답하세요"라는 문제를 보면 직감적으로 전체 탐색을 떠올리면 좋다.

 

이번 문제는 first, second에 주어진 모든 주제에 대해 몇 명의 사람이 관심을 갖고 있는지 확인하고 그 최댓값을 리턴해서 풀 수 있다. 즉, 간단하게 정리하면 다음과 같은 단계로 문제를 해결할 수 있다.

 

① 화제를 순서대로 선택한다

② 해당 화제에 대해 몇 명이 관심이 있는지 조사한다

 

 

 책의 해설에서는 for 문을 사용해 화제를 차례대로 선택하고, 그 주제에 관심이 있는 사람을 선택하는 것도 for 반복문을 사용하는 해법을 제시한다.

 

하지만 Python을 사용하면 collections 라이브러리의 Counter을 사용해 등장한 화제의 빈도를 체크하고, 최댓값을 리턴하여 문제를 해결할 수 있다.

 

---

Python

from collections import Counter
 
def InterestingParty(first , second):
  # step 1. 모든 관심사를 모으기
  all_topics = first + second
 
  # step 2. Counter을 통해 가장 빈번하게 발생한 토픽의 개수 찾기
  all_topic_count = Counter(all_topics)
 
  # step 3. 최대 값을 찾아서 리턴하기
 
  return max(all_topic_count.values())

 

line 1 : collections의 Counter 임포트

line 5 : all_topics 리스트에 first와 second에 주어진 화제를 모음

line 8 : all_topic_count 딕셔너리에는 all_topics에 등장한 화제가 key, 그 빈도가 value로 저장됨

line 12 : value의 최댓값이 가장 많은 사람이 관심사를 가진 화재의 빈도수

 

 

Test Case 실행 예시 :

 

 

출처 : TopCoder 알고리즘 트레이닝, 타카하시 나오히로 지음

본 포스팅은 [TopCoder 알고리즘 트레이닝] 책의 내용을 바탕으로 Python 코딩한 내용입니다.

---