문제를 보자마자 너무 길어서 일단 읽기가 싫어졌었다.. 하지만 마음을 다잡고 접근해보았다.
1. 오늘의 학습 키워드
- 해쉬
- 리스트
- min
2. 문제: 폰켓몬
문제 설명
당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.
- 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
- 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
- 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
- 두 번째(1번), 세 번째(2번) 폰켓몬을 선택
- 두 번째(1번), 네 번째(3번) 폰켓몬을 선택
- 세 번째(2번), 네 번째(3번) 폰켓몬을 선택
이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.
당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.
제한 사항
- nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
- nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
- 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
- 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.
입출력 예
| nums | result |
|---|---|
| [3,1,2,3] | 2 |
| [3,3,3,2,2,4] | 3 |
| [3,3,3,2,2,2] | 2 |
입출력 예 설명
- 입출력 예 #1
문제의 예시와 같습니다. - 입출력 예 #2
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리, 2번 폰켓몬 한 마리, 4번 폰켓몬 한 마리를 고르면 되며, 따라서 3을 return 합니다. - 입출력 예 #3
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리와 2번 폰켓몬 두 마리를 고르거나, 혹은 3번 폰켓몬 두 마리와 2번 폰켓몬 한 마리를 고르면 됩니다. 따라서 최대 고를 수 있는 폰켓몬 종류의 수는 2입니다.
3. 나의 풀이
접근 방법
n마리의 폰켓몬이 주어지면 n/2마리의 폰켓몬을 코르되, 가장 많은 종류의 폰켓몬을 골라야 한다.
nums = [3,1,2,3]이면, 2마리의 폰켓몬을 골라야 한다.
이때, 1번, 2번 / 2번, 1번 / 1번, 3번 / 3번, 1번 / 2번, 3번 / 3번, 2번의 총 6가지가 발생하는데 여기서 가장 많은 종류인 2종류의 폰켓몬을 고를 수 있다.
여기서 나는 우선 겹치는 폰켓몬을 제거하기 위해 set() 을 사용했다.
set(nums) = {3,1,2}이 나오는데
len(set(nums))는 3이 된다. 우리는 2마리를 선택해야 하는데 이것은 len(nums)/2 로 구할 수 있다.
즉, 중복되지 않도록 nums을 집합 자료형 set(nums)형태로 만들고, 이것의 길이와 len(nums) / 2의 결과를 비교해서 더 작은 값을 return 하면 된다.
3번 예시를 보면 더 확실히 알 수 있다.
nums = [3,3,3,2,2,2] 의 길이는 6이므로 여기서 3마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택해야한다.
set(nums) = {3,2}, 길이는 2, len(nums) / 2 = 3이다.
3마리를 골라야 하는 상황에서 중복되지 않게 고를 수 있는 폰켓몬은 2마리 뿐이다. 이럴 경우 2마리를 return하게 되고 이 조건은 다음과 같이 작성할 수 있다.
if len(set(nums)) > len(nums) / 2 : # 입출력 예 1
return len(nums) / 2
else:
return len(set(nums)) # 입출력 예 2, 3이것을 더 간단히 한다면 아래와 같이 작성할 수 있다.
def solution(nums):
return min(len(set(nums)),len(nums)/2)4. 다른 풀이 (hash)
이 문제는 해시 카테고리에 속해있는 문제이므로 해시 자료구조를 활용해서 코드를 다시 구현해보자.
처음에는 어떻게 이 문제가 해시인거야? 막막했다.
일단 파이썬에서 해시는 딕셔너리로 나타낼 수 있다.
딕셔너리를 만들어보자.
dict = {}
for n in nums:
dict[n] = 1 # 이렇게 작성하면 중복되는 폰켓몬은 제거된다. # 키는 폰켓몬, 값은 1
위와 같이 작성하면 같은 종류의 폰켓몬은 같은 해시 값을 가지게 되면서 중복이 제거 된다
set(nums) 와 동일한 방법이라 볼 수 있다.
그렇다면, 여기서 이전 방법과 동일하게 len(nums) / 2와 비교를 진행하는 것이다. 이것을 완성하면 코드는 아래와 같다.
def solution(nums):
dict = {}
for n in nums:
dict[n] = 1 # 이렇게 작성하면 중복되는 폰켓몬은 제거된다. # 키는 폰켓몬, 값은 1
if len(nums) / 2 > len(dict):
return len(dict)
return len(nums) / 2 5. 결론
다양한 방법으로 진행을 해보았다. 문제가 길었지만 실제로 코드를 구현하면 짧았다. 문제의 핵심을 이해한다면 코드가 짧아지는 문제라고 볼 수 있다. 해쉬 카테고리에 속해있는것은 약간 억지(?) 같았지만 해쉬로 풀 수 있는것은 맞으니까 뭐,,,,
이 문제를 통해서도 알 수 있는건 같은 자료구조, 알고리즘에 속해 있는 문제들을 여러 개 풀어야 한다는 것이다. 그러면 자연스럽게 해당 알고리즘, 자료구조를 잘 파악할 수 있는것 같다.
읽어주셔서 감사합니다!
