CodingTest/해시 알고리즘

프로그래머스 (Level 1) - 폰켓몬

seongduck 2022. 7. 29. 15:26

1. 문제 설명

폰켓몬은 종류에 따라 번호를 붙여서 구분한다. 즉, 같은 종류의 폰켓몬은 같은 번호를 가지고 있다. 

  • 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 3번 폰켓몬은 2마리 1번, 2번 폰켓몬은 각각 1마리씩 있다.
  • 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같다.
      1. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
      2. 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
      3. 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
      4. 두 번째(1번), 세 번째(2번) 폰켓몬을 선택
      5. 두 번째(1번), 네 번째(3번) 폰켓몬을 선택
      6. 세 번째(2번), 네 번째(3번) 폰켓몬을 선택
  • 따라서 위 예시의 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 된다. 
  • 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려고 한다.
  • N마리의 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return해라

2. 제한사항

  • nums는 폰켓몬의 종류 번호가 담긴 1차원 배열이다.
  • nums의 길이는 1 < N < 10000이하의 자연수이며 항상 짝수이다.
  • 폰켓몬의 종류 번호는 1이상 200000이하의 자연수로 나타낸다.
  • 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 retrun하면 된다.

3. 입출력 예

배열 최댓값
nums result
[3,1,2,3] 2
[3,3,3,2,2,4] 3
[3,3,3,2,2,2] 2

4. 풀이 접근

  1. 중복 제거한다.
  2. 중복 제거한 개수 <= N/2면 result는 중복 제거한 개수
  3. 중복 제거한 개수 > N/2면 result는 N/2

 


5. 코드

def solution(nums):
    set_nums = len(set(nums)) #1) 중복제거
    select = len(nums) / 2
    
    if(set_nums <= select): # 2) 
        return int(set_nums)
    if(set_nums > select): # 3)
        return int(select)

6. 알아둘만한 문법

# list 개수, key 개수
result = len(a)