[TopCoder 알고리즘] 전체탐색

코딩

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

LittleFox 2022. 4. 1. 20:39

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12

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())

cs