[해시] 폰켓몬 (프로그래머스, Level 1)

Soorim Yoon·2022년 9월 12일

코테 해시

알고리즘 & 코딩테스트

목록 보기

11/67

문제

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

N마리 포켓몬에 각각 번호가 매겨져 있다.
ex) [3, 1, 2, 3] : 3번, 1번, 2번, 3번
N/2 마리를 뽑을 때 포켓몬 종류를 최대한 다양하게 뽑을 수 있는 경우를 구해라.
이 때 중복되지 않은 포켓몬의 종류는 몇 가지인지 구해라.

풀이

처음에는 조합을 사용해 직접 nums 배열 속의 포켓몬 번호를 조합하여, 중복되지 않은 포켓몬의 개수를 셌다. 이후 가장 큰 값을 골라 출력했다.
해당 방법은 시간 초과 문제를 나타냈다. 생각해보니 nums에 들어있는 포켓몬의 수가 매우 많을 경우, 가능한 모든 조합을 해보고 개수를 세고, 그 숫자 중 가장 큰 값을 고르는 과정에서 시간 복잡도가 증가했을 것이다.
다양한 풀이법을 검색하던 중, 직접 조합하지 않고도 개수를 알 수 있는 방법을 발견하였다. 알고리즘은 다음과 같다.

뽑을 캐릭터의 수(N/2)와 nums 배열 안 중복되지 않는 캐릭터의 수를 비교한다. 뽑을 캐릭터의 수(pick)가 중복되는 캐릭터의 수(count)보다 작은 경우, 정답은 뽑을 캐릭터의 숫자(pick)이다. 뽑을 캐릭터의 수(pick)가 중복되지 않는 캐릭터의 수(count)보다 큰 경우, 정답은 중복되지 않는 캐릭터의 수(count)이다.

pick < count : answer = pick

pick > count : answer = count

예시

예시를 통해 설명하겠다.
1) nums : [3, 1, 2, 3]
2) nums : [3, 3, 3, 2, 2, 4]
3) nums : [3, 3, 3, 2, 2, 2]

1)의 경우 뽑을 캐릭터 수는 N/2 = 4/2 = 2 이다. 중복되지 않은 캐릭터의 수는 3개(1, 2, 3번)이다. 두 개의 캐릭터를 뽑으므로 중복되지 않으면서 최대로 뽑을 수 있는 캐릭터의 수는 2개이다. 따라서 pick 값이 정답이 된다.
3)의 경우 뽑을 캐릭터의 수는 N/2 = 6/2 = 3 이다. 중복되지 않은 캐릭터의 수는 2개(2, 3번)이다. 세 개의 캐릭터를 뽑는데 중복되지 않으면서 최대로 뽑을 수 있는 캐릭터의 종류는 2개이다. 따라서 count 값이 정답이 된다.

코드

👍 정답 (수정한 코드)

# 시간 초과 문제를 해결함
# 처음에는 순열(combination)을 통해 직접 뽑고, 뽑은 값의 중복을 제거해 개수를 세서 가장 개수가 많은 것을 출력함
# => 다른 방법을 찾아보면서 직접 뽑고 추릴 필요가 없음을 깨닫고 아래 방법으로 진행

def solution(nums):
    pick = len(nums)//2   # 뽑아야 하는 캐릭터의 개수
    count = len(set(nums))      # nums에 저장된 캐릭터 숫자의 중복을 제거한 후 개수 (중복을 제거한 캐릭터 개수)
    
    if pick < count:    # 뽑을 캐릭터 개수가 전체 캐릭터 개수(중복 x)보다 작은 경우
        answer = pick       # 뽑을 캐릭터 수가 정답이다
    else:
        answer = count  # 뽑을 캐릭터 개수가 전체 캐릭터 개수(중복 x)보다 큰 경우, 전체 캐릭터 개수가 정답
    
    return answer

위와 동일한 아이디어로 구현한 코드

def solution(nums):
    answer = 0
    kind = len(set(nums))
    
    if kind > len(nums)/2:
        answer = len(nums)/2
    else:
        answer = kind
    
    return answer

처음 코드

1), 2)번 방법 모두 조합을 통해 모든 가능성을 직접 구하는 연산을 진행하였기 때문에 시간 복잡도가 매우 높다.

1) 조합(combination) 사용, 반복문을 통한 리스트 중복 요소 제거

from itertools import combinations

# 1) 리스트 중복 요소 제거 : for문(반복문) 사용하기
def solution(nums):
    comb = list(combinations(nums, len(nums)//2))
    
    lens = []
    for arr in comb:
        alist = []
        for i in range(len(arr)):
            if arr[i] not in alist:
                alist.append(arr[i])
        lens.append(len(alist))
    
    answer = max(lens)
        
    return answer

2) 조합(combination) 사용, set 연산을 통한 리스트 중복 요소 제거

# 2) 리스트 중복 요소 제거 : set 연산 사용하기

from itertools import combinations

def solution(nums):
    comb = list(combinations(nums, len(nums)//2))
    
    lens = []
    for arr in comb:
        alist = list(set(arr))
        lens.append(len(alist))
    
    answer = max(lens)
        
    return answer