프로그래머스 고득점 Kit - 폰켓몬 Python

Problem

https://school.programmers.co.kr/learn/courses/30/parts/12077

프로그래머스

 

연구실에 있는 $N$ 마리의 폰켓몬 중, $\frac{N}{2}$ 마리를 가져가도 된다.

폰켓몬은 종류에 따라 번호를 붙인다. 

이중 가장 많은 종류의 폰켓몬을 가져갈 때, 그 종류의 개수를 return 해야 한다.

 

Input / Output Example

nums는 폰켓몬의 종류 번호가 담긴 1차원 배열이다.

 

nums: [3,1,2,3]

output: 2

Solution

 

해당 문제는 해시 카테고리로 분류되어 있다.

즉 해시를 사용하라는 문제이다.

 

파이썬의 set 자료구조는 해시함수를 이용해 해시테이블이라는 자료구조를 통해 데이터를 저장한다.

따라서 중복을 가질 수 없다.

 

이 자료구조를 활용하면, 리스트에서 중복을 쉽게 제거할 수 있다.

 

우리는 최대 $\frac{N}{2}$ 만큼 가져갈 수 있기에,

들어온 nums 리스트의 길이를 반으로 나눈다.

 

그 다음 nums 리스트를 set 자료구조를 통해 구해 중복을 제거하고,

set의 길이를 구한다

 

만약 set의 길이가 nums 리스트의 길이보다 작거나 같다면 

겹치는 종류가 있어 $\frac{N}{2}$ 보다 작아지기에 set의 길이를 반환하면 된다.

 

반면에 set의 길이가 nums 리스트이 길이보다 크면

아무리 많이 가져가도 최대 $\frac{N}{2}$ 만큼 가져갈 수 있으니 이 값을 반환한다.

 

Code

def solution(nums):
    length = nums.__len__() // 2
    set_nums = set(nums)
    set_length = set_nums.__len__()
    if set_length <= length:
        return set_length
    else:
        return length

 

여기서 리스트나 set 자료구조의 길이를 구하는 것은

파이썬이 내부에서 데이터가 추가되고 삭제될 때 미리 길이값을 구한다.

따라서 길이를 구하는 코드의 시간복잡도는 $O(1)$ 이다.

 

해당 코드는 얼핏 보면 시간복잡도가 $O(1)$ 인 것 처럼 보이지만,

set을 통해 리스트 내에 있는 인자를 하나하나 순회하며 set을 만든다.

따라서 해당 코드의 시간 복잡도는 $O(N)$ 이다.