[프로그래머스] 해시 - 폰켓몬 (Python)

안녕하세요. 탁입니다.

두번째 문제는 해시 유형의 Level1 문제인 '폰켓몬' 입니다.

완주하지 못한 선수

문제 설명

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 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 하면 됩니다.

입출력 예

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.

가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리, 2번 폰켓몬 한 마리, 4번 폰켓몬 한 마리를 고르면 되며, 따라서 3을 return 합니다.

입출력 예 #3

6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.

가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리와 2번 폰켓몬 두 마리를 고르거나, 혹은 3번 폰켓몬 두 마리와 2번 폰켓몬 한 마리를 고르면 됩니다. 따라서 최대 고를 수 있는 폰켓몬 종류의 수는 2입니다.

나의 풀이

문제 접근 아이디어는 이랬습니다.

입출력 예시의 2번과 3번에서 확인할 수 있듯이 N/2를 선택해야하기 때문에, 가장 많은 종류를 선택하는 경우는 두 가지 케이스다.

1. nums 길이/2가 폰켓몬 종류보다 큰 경우
2. nums 길이/2가 폰켓몬 종류보다 작은 경우

nums 길이/2가 폰켓몬 종류보다 큰 경우에는 (예시 3번)

폰켓몬 종류 수가 곧 선택된 가장 많은 종류 값이다.

nums 길이/2가 폰켓몬 종류보다 작은 경우에는 (예시 2번)

nums 길이/2 수가 곧 선택된 가장 많은 종류 값이다.

그러니 두 값을 비교해서 반환하면 되겠다.

1. 초기화 상태

def solution(nums):
    answer = 0
    return answer

2. 풀이 과정

from collections import Counter
def solution(nums):
    answer = 0
    print(len(nums)//2)
    print(len(Counter(nums).keys()))
    print(min(len(nums)//2,len(Counter(nums).keys())))
    return answer

3. 답안 확인

from collections import Counter
def solution(nums):
    return min(len(nums)//2,len(Counter(nums).keys()))

테스트케이스도 모두 성공했으니 답안을 제출해봅니다.

제출 답안 분석 및 복잡도 확인

Gemini의 도움을 받아 저의 답안에 대한 평가를 해봅니다.

1. 시간 복잡도: $O(N)$

• len(nums) // 2: 리스트의 길이를 조회하고 2로 나누는 연산은 $O(1)$입니다.
• Counter(nums): $N$개의 원소를 순회하며 해시 테이블에 빈도를 누적 집계하므로 $O(N)$이 소요됩니다.
• len(Counter(nums).keys()): Counter 객체의 .keys()는 딕셔너리 키 뷰(dict_keys)를 반환하며, len() 호출 시 해시맵의 내부 크기 메타데이터를 바로 조회하므로 $O(1)$입니다.
• min(...): 두 정수의 대소 비교이므로 $O(1)$입니다.종합 결론: 전체 시간 복잡도는 $O(N)$입니다. $N \le 10,000$ 제한 조건에서 0.01초 이내에 매우 빠르게 통과합니다.

2. 공간 복잡도: $O(K) \approx O(N)$

• Counter(nums) 객체는 서로 다른 폰켓몬 종류 수($K$)만큼의 키-값 쌍(종류 번호, 빈도수)을 저장합니다.
• 최악의 경우 모든 폰켓몬의 종류가 다를 때($K = N$), 최대 $O(N)$의 메모리를 사용합니다.
• 종합 결론: 전체 공간 복잡도는 $O(N)$입니다.

3. 제출 답안 총평

• 장점: 문제의 핵심 로직인 "최대 선택 가능 수($N/2$)와 총 종류 수 중 최솟값 반환"을 한 줄로 명확하게 파악하여 구현했습니다.
• 아쉬운 점:
  1. 불필요한 빈도수 집계: 이 문제는 각 폰켓몬이 몇 번 등장했는지(빈도수)는 전혀 알 필요가 없고, 서로 다른 종류가 몇 개인지만 알면 됩니다. Counter는 각 원소마다 등장 횟수를 덧셈 갱신하므로 불필요한 연산 오버헤드가 발생합니다.
  2. 불필요한 메서드 호출: Counter 객체 자체에 len()을 직접 취해도(len(Counter(nums))) 키의 개수가 반환되므로, .keys()를 명시적으로 호출할 필요가 없습니다.

AI 추천 답안

아래는 Gemini가 작성해 준 내용입니다.

사용 AI 모델: Gemini 3.8 Flash (Extended)

추천: set (집합) 자료구조 사용

중복을 제거하여 고유 원소의 개수를 구할 때는 set(집합) 자료구조를 사용하는 것이 가장 직관적이고 표준적인 접근 방식입니다.

def solution(nums):
    # 고유 폰켓몬 종류 수와 최대로 가져갈 수 있는 수(N // 2) 중 최솟값 반환
    return min(len(nums) // 2, len(set(nums)))

• 동작 원리: 파이썬의 set은 해시 테이블 기반으로 중복을 자동으로 제거합니다. set(nums)로 유일한 폰켓몬 종류들만 남긴 뒤, 그 길이(len)와 len(nums) // 2 중 작은 값을 반환합니다.

제출 답안 vs AI 추천 답안 비교

Counter를 활용한 접근도 시간 복잡도 관점에서는 동일하게 $O(N)$을 만족하여 코딩테스트 통과에는 문제가 없습니다. 그러나 "개수 세기(카운팅)"가 아닌 "종류 수(중복 제거)"를 구하는 문제에서는 빈도수 필드를 함께 할당하는 딕셔너리 계열보다 set을 사용하는 것이 메모리와 런타임 상수 계수를 줄일 수 있으며, 코드의 의도 또한 훨씬 명확하게 드러납니다.

회고

업무에 java 위주로 사용해서라는 핑계도, AI한테 요즘에는 코딩을 다 맡긴다는 핑계도 모두 핑계인 결과...!

아이디어 자체는 맞는 방향이었지만 아쉽네요.

set()을 잘 활용해보겠습니다.

바로 다음 문제도 또 공부해보겠습니다.

감사합니다.