[프로그래머스] 폰켓몬

문제 설명
당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.
(1) 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
(2) 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
(3) 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
(4) 두 번째(1번), 세 번째(2번) 폰켓몬을 선택
(5) 두 번째(1번), 네 번째(3번) 폰켓몬을 선택
(6) 세 번째(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 하면 됩니다.

풀이 00

1. 중복 제거 → "해시"
2. N/2 선택

def solution(nums):
    answer = list(dict.fromkeys(nums)) 
    
    if (len(nums) // 2) <= len(answer):
        return (len(nums) // 2)
    
    return len(answer)

파이썬에서 해시(Hash)는 Dictionary 라는 자료구조를 통해 해시를 제공하며, Dictionary는 dict클래스로 구현한다.
+) 파이썬의 set, dict자료구조는 해시 테이블을 이용

딕셔너리는 key, value로 데이터를 이루게 되는데 이 key 값이 중복 불가의 성질이 있다! 이 성질을 이용해서 list에서 중복을 제거를 하고자 한다. dict.fromkeys를 통해 nums(리스트 자료형)를 중복 제거된 키 값들로 변환하도록 한다.

fromkeys는 key값을 딕셔너리 자료형으로 만들어 주는 작업을 하는 메서드이다. 해당 메서드를 이용하게 될 경우, 리스트의 값들을 딕셔너리의 key값들로 변환해준다면 중복이 제거가 될 것이다.

이후, 중복이 제거된 key값들을 다시 리스트로 변환하도록 한다.

• 해시(Hash)의 사용 용도

1. 인덱스 값이 '문자열' 혹은 '튜플'인 경우
   리스트의 경우, 숫자 인덱스를 사용하여 원소에 접근을 해야 함
   ex) list[1] : (O) / list['a'] : (X)
2. 빠른 접근 및 탐색이 필요할 경우
   딕셔너리 함수의 시간 복잡도는 대부분 O(1)로, 매우 빠른 자료구조
   *아래 표의 경우, 딕셔너리와 리스트의 시간 복잡도 차이를 나타냄

• Operation	Dict	List
  Get Item	O(1)	O(1)
  Insert Item	O(1)	O(1) ~ O(N)
  Update Item	O(1)	O(1)
  Delete Item	O(1)	O(1) ~ O(N)
  Search Item	O(1)	O(N)

  원소를 넣거나 삭제, 찾는 일이 많을 경우, 딕셔너리를 사용하는 것이 좋음

3. 집계가 필요한 경우
   코딩 테스트의 경우, 원소의 개수를 세는 문제가 다수 출제
   이때, 해시와 collections 모듈의 Counter 클래스를 사용할 경우 빠른 문제 풀이가 가능

풀이 01

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

min 함수를 활용하여 (1) 리스트의 길이를 2로 나눈 값과 (2) 리스트에서 중복을 제거한 후의 길이를 비교하여 2가지 중 작은 값을 반환하도록 한다.

---

참고

• Hash
• 리스트 중복제거