[Programmers] 폰켓몬

, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.
당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

풀이 과정

문제를 읽고 이해하는 것에도 다소 시간이 소요됬지만 그걸 코드로 쓰는 과정에서도 생각을 조금 해야했었다. 조합을 이용한 풀이 방법을 떠올렸기 때문에 combination을 이용해 풀었지만 시간초과가 나서 다른 방식으로 개선해나갔다.

첫 번째 시도

from itertools import combinations

def solutions(nums):
    answer = 0
    N = len(nums) // 2

    for x in combinations(nums, N):
        selections = set(x)
        answer = max(len(selections), answer)

    return answer

단순히 조합을 만들어 순회하면서 최대값을 찾는 걸로 구현했다. 그런데 당연하게도 시간초과가 난다.

두 번째 시도

두 번쨰 시도는 다음과 같다. 이 떄부턴 정답이었다.

from itertools import combinations

def solution(nums):
    N = len(nums) // 2

    set_nums = list(set(nums))

    if len(set_nums) > N:
        answer = 0
        for comb in combinations(set_nums, N):
            if answer < len(comb):
                return len(comb)

    return len(set_nums)

접근 방법은 다음과 같다.

• 입력받은 배열에서 중복을 제거한 원소들만 남긴다.(set_nums)
  • 조합을 이용한 풀이에서 2가지 원소를 택하게 되는데 이 떄 발생되는 리스트의 길이를 줄이기 위함임
• set_nums의의 길이가 nums의 N/2 보다 클 경우
  • 조합을 이용한 리스트의 길이의 원소의 max 값을 구해 리턴한다.
• 그 외
  • set_num의 길이를 바로 리턴

세 번째 시도

'두 번째 시도'의 코드를 살펴보니 같은 말을 하고 있는 코드가 있어서 다음과 같이 개선했다.

from itertools import combinations

def solution(nums):
    N = len(nums) // 2

    set_num = list(set(nums))

    if len(set_num) > N:
        return N

    return len(set_num)

결과는 두 번째 시도와 거의 동일하다.