[Python] 프로그래머스 알고리즘 해시 - 폰켓몬

 

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

프로그래머스

 

문제설명

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 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 함수를 완성해주세요.

 

 

제한사항

1. nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
2. nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
3. 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
4. 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

 

 

해결전략

일단 해시 문제였기 때문에 딕셔너리를 사용해야겠다는 생각이 들었다. 사실 항해 이후로 이렇게 긴 문제를 처음 풀어보는데... 

문제를 이해하는 것이 제일 중요하다고 생각했다.

📌 해시: 키(Key) 와 값(Value)  로 이루어진 데이터 구조
파이썬의 대표적인 해시로는 딕셔너리 타입이 있다. 

 

💡 문제의 핵심은 주어진 포켓몬 종류 배열 nums에서 최대한 다양한 종류의 포켓몬을 N/2 마리 선택하는 것이다.

     그렇다면 우리는 최대 고를 수 있는 N/2 개의 수와 / 다양한 종류가 포함된 N/2 를 생각해볼 필요가 있다. 

     경우의 수가 많고 최대 최소가 나오기 때문에 선택할 수 있는 수를 잘 찝어내는 것이 중요하다.

 

💡 다양한 종류를 원한다? = 중복을 제거해야한다. 

한가지의 수가 많아봤자 우리가 원하는 조건을 충족시키지는 않는다는 것이다. 따라서 중복을 제거해야 종류만 따질 수 있다.

 

 

🤔 최댓값이니까 max? 

사실 이 부분에서 조금 헷갈렸다... 처음에는 당연히 최댓값이니까 max 라고 했다가 오류가 나서 ㅎㅎ...

이 부분이 왜 max 가 아니라 min인지를 설명해보도록 하겠다.

 

우리는 지금 두가지 상황을 고를 수 있는 것이다.

1. 고유한 폰켓몬 종류가 N/2보다 적거나 같은 경우:
   • 예를 들어, nums = [1, 1, 2, 2, 3, 3]에서 중복이 제거된, 고유한 폰켓몬 종류는 3가지(1, 2, 3) 이다. N/2는 3이므로, 최대 3가지 종류의 폰켓몬을 선택할 수 있다.
2. 고유한 폰켓몬 종류가 N/2보다 많은 경우:
   • 예를 들어, nums = [1, 2, 3, 4, 5, 6]에서 중복이 제거된, 고유한 폰켓몬 종류는 6가지(1, 2, 3, 4, 5, 6)이다. 하지만 N/2는 3이므로, 최대 3가지 종류의 폰켓몬을 선택할 수 있다.

=> 따라서!! 아무리 고유한 종류가 많더라도 N/2 개로 갯수제한이 되고, 아무리 배열에 있던 수가 많더라도 중복되는 수가 많으면 의미가 없기 때문에 둘을 고려하여 더 적은 숫자로 가져와야한다는 것이다!

 

첫번째 시도

def solution(nums):
    dict = {}
    # 배열 순회하면서 딕셔너리에 요소 추가 (중복 제거)
    for n in nums:
        dict[n] = 1 # 원래 0으로 하려다가 조금 오류가 있을 것 같아 1로 수정 ( 여기 숫자는 상관없다) 
    
    # 중복 제거된 요소의 개수
    pocketmons = len(dict)
    
    # 배열 길이의 절반
    half_pocketmons = len(nums) // 2
    
    # 중복 제거된 요소의 개수와 배열 길이의 절반 중 작은 값 반환
    return min(pocketmons, half_pocketmons)

 

📌 point ! 딕셔너리에는 중복된 값이 제거된 상태로 저장이 된다. (** 딕셔너리는 키의 중복을 허용하지 않음 ** ) 

 

따라서 빈 딕셔너리를 만들고, 

입력받는 숫자인, nums 배열의 각 요소들을 순회하며 반복문을 실행한다. 따라서 n 을 키(Key) 로, 1을 값(Value) 로 하여 딕셔너리에 저장하는데, 중복을 허용하기 않기 때문에 nums 에 저장이 되지 않는다.

이렇게 하여 중복이 제거된 숫자와 배열길이의 절반 중 작은 값을 가져오도록 길이를 비교해준다.

 

두번째 시도

🤔 중복을 제거한다라... 어디서 많이 들어보지 않았는가?? ! 중복을 허용하지 않는 것! 바로바로 set 이 있었다.

어차피 둘다 중복을 제거한 상태를 만드는 것이 전제조건이기 때문에 

set 을 활용하여 중복을 제거한 변수를 만들어주었다. 

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

 

결과는 매우 굿!

오랜만에 코테 문제를 푸니..실력이 더 줄어든것 같다 ㅋㅋ...

열심히 해야겠당