Level 2 폰켓몬 Python3

programmers.co.kr/learn/courses/30/lessons/1845?language=python3

코딩테스트 연습 - 폰켓몬

 

최종 코드

• GitHub github.com/hwayeon351/Programmers-Algorithms

hwayeon351/Programmers-Algorithms

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

 

---

풀이 과정 

풀이 시간  17분

 처음 문제에 접근했을 때, 조합을 구해서 각각의 경우의 수마다 서로 다른 종류의 폰켓몬들을 카운팅해서 가장 큰 수를 반환하도록 했었다. 제출 해보니 절반 정도 시간초과로 문제 풀이에 실패했다.

다른 방법으로 시도해야 함을 깨닫고, 다시 문제를 읽어나가다 보니 방법이 떠올랐다. 애초에 모든 경우의 수를 구하지 않더라도 입력으로 주어지는 nums에 서로 다른 종류의 폰켓몬이 몇 마리 있는지를 파악한 후, 그 수가 N/2보다 많은지 적은지를 따져주면 되는 것이었다.

예를 들어, nums = [3, 3, 4, 5, 6, 4]라고 해보자. 그러면 nums에는 서로 다른 폰켓몬의 종류가 3, 4, 5, 6으로 4가지이다. 그리고 N/2 = 3마리의 폰켓몬을 고를 수 있기 때문에, (3, 4, 5), (4, 5, 6), (3, 5, 6), (3, 4, 6)으로 최대 서로 다른 세 종류의 폰켓몬을 고를 수 있다. 어차피 정답은 최대 고를 수 있는 서로 다른 종류의 수만 출력하면 되기 때문에, 입력으로 주어진 서로 다른 폰켓몬의 종류 수와 N/2 값만 비교하면 된다. 

그리고 서로 다른 폰켓몬의 종류 수는 리스트인 nums을 set으로 변환한 다음, len으로 크기를 출력해보면 알 수 있다.

1. nums의 서로 다른 폰켓몬의 종류 수 = len(set(nums)), 뽑을 수 있는 폰켓몬의 수 = len(nums)//2를 각각 구한다.
2. nums의 서로 다른 폰켓몬의 종류 수가 N/2보다 많으면 len(nums)//2를 출력하고, 적으면 len(set(nums)를 출력한다.

따라서, len(set(nums))와 len(nums)//2 중 작은 값을 반환하면 정답이다.

 

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