[프로그래머스] 폰켓몬(python)

2021년 5월 14일 Algorithm, 프로그래머스, 폰켓몬

 

* 문제 분석

 

폰켓몬의 문제

 

- 폰켓몬의 종류가 주어진 배열으로부터 고를 수 있는 고를 수 있는 최대한 다양한 폰켓몬의 종류를 구하는 문제이다.

- 중복된 폰켓몬은 무시하고, 서로 다른 폰켓몬을 최대한 골라야 한다.

 

* 문제 제한 사항과 입력 예시

 

문제 제한 사항과 입력 예시

- 폰켓몬의 종류가 담긴 배열 nums가 주어진다.

- 폰켓몬의 종류가 담긴 배열 nums의 길이는 10,000 이하의 짝수인 자연수이다.

- 폰켓몬의 종류는 1 ~ 200,000의 자연수이다.

- 다양한 폰켓몬의 종을 고르는 최대의 경우가 있을 수 있으나, 상관없이 최대로 다양한 폰켓몬을 고를 수 있는 수만 반환한다.

 

* 풀이

 

 

# line 2 : 고른 폰켓몬이 담길 배열이다.

# line 3 : 주어진 배열을 순회한다. 각 폰켓몬의 종류를 조회한다.

# line 4 ~ 5 : 고른 폰켓몬이 골라야 하는 폰켓몬의 최대 수보다 클 경우, 더 이상 폰켓몬을 살피지 않는다.

# line 7 ~ 8 : 만약 내가 고르지 않은 폰켓몬이 등장할 경우 고른다.

# 고른 폰켓몬의 갯수를 반환한다.

- 문제 조건에서 최대한 다양한 종류의 폰켓몬을 고를 수 있는 경우만 반환한다는 조건에 의해서 이와 같이 풀었다.

- 고르는 문제로 생각하고 combinations를 사용하려고 했으나, test case에서 시간초과가 발생하였다.

 

* 개선된 풀이 방법

 

- 보다 더 간단한 코드를 통해 문제를 해결할 수 있다.

- 문제에서 얻을 수 있는 중요한 힌트 중 하나는 고를 수 있는 폰켓몬들의 종류가 모두 겹치지 않는다고 가정하였을 때, 문제 조건에 N // 2가지 폰켓몬을 고르는 것이 최대가 된다.

    return min(len(nums) // 2, len(set(nums)))

- 위 코드와 같이 최대로 고를 수 있는 폰켓몬의 수와, 실제 배열 내에 존재하는 폰켓몬들의 종류를 비교하여, 더 작은 값을 출력하면 얻을 수 있다.