[알고리즘] 해시 - 폰켓몬

https://school.programmers.co.kr/learn/courses/30/lessons/1845

프로그래머스

 

Q. 

# N마리 중 N/2마리 선택
# 2마리가 같은 번호이면 따로 카운트 X
# 최대한 다른 종류 선택 (3123번 존재 시, 33 선택을 지양)
# input: 값 종류 nums array
# output: 종류 nums

 

✅ 조건 정의

1. n/2 개를 선택가능
2. n/2 개 선택 중 종을 가장 다양하게 선택
3. 그렇다면 n/2가 종의 수보다 크면 종의 수만큼 선택
4. 아니라면 n/2가 종의 수보다 작다면 n/2를 출력

A1.

def solution(nums):
    size_count = {} # 폰켓몬 종류 nums array 초기화
    for size in nums:
        if size in size_count: # 새로운 종류 num이 기존에 존재하는지 확인
            size_count[size]+=1 # 존재하면 size를 1 증가시킴
        else:
            size_count[size]=1 # 없으면 추가하고 size를 1로 설정
    sorted_counts = sorted(size_count.values(), reverse=True) # N:폰켓몬 종류별 개수(size) N 저장
    
    
    return answer

 

test input

: [3,1,2,3]

solution([3, 1, 2, 3])

size_count = {} # 폰켓몬 종류 nums array 초기화
 for size in nums:
  if size in size_count: # 새로운 종류 num이 기존에 존재하는지 확인
   size_count[size]+=1 # 존재하면 size를 1 증가시킴
  else:
   size_count[size]=1 # 없으면 추가하고 size를 1로 설정         
>> {3: 2, 1: 1, 2: 1}

sorted_counts = sorted(size_count.values(), reverse=True) # N:폰켓몬 종류별 개수(size) N 저장
>> [2, 1, 1]

you_take = int(sum(sorted_counts)/2) # 선택 가능한 개수 N/2 저장, int로 변환
>> 2

 

✅ 최대 선택 가능한 폰켓몬의 개수는 서로 다른 종류의 포켓몬(sorted_counts) 개수의 max이어야 하지만, you_take로 제한된다. (=N/2보다 클 수 없음) → min() 활용

answer = min(len(sorted_counts),you_take) # 최대한 다른 종류를 선택하기 위해 min(N/2) 출력
>> 2

 

A2.

: len()으로 입력된 선택 가능한 폰켓몬 수 구하고, set()으로 고유값(=서로 다른 종류 폰켓몬 수) 구함

def solution(nums):
    N = len(nums) // 2 # //는 정수형으로 나눈 몫을 출력함
    uniq = list(set(nums))
    return min(len(uniq), N)

A3.

def solution(nums):
    return min(len(set(nums)), len(nums)/2)

 

---

답변 비교

https://school.programmers.co.kr/learn/courses/30/lessons/1845/questions

프로그래머스