[프로그래머스]폰켓몬

[34] 폰켓몬

책 구매하기

문제 정보

• 분류: 집합
• 정답률: 63%
• 권장 시간 복잡도: O(N)
• 핵심 키워드: 집합, 중복 제거, 최대 종류 수, min
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/1845

문제를 읽을 때 체크할 포인트

결국 고를 수 있는 최대 마릿수는 N//2이고, 종류 수는 set으로 바로 구해진다. 그래서 답은 '종류 수'와 '선택 가능한 수' 중 작은 값 하나로 끝난다.

연결 여부를 다시 계산하면 비효율이 커진다. 이미 같은 편인지 아닌지를 빠르게 확인할 수 있어야 하고, 그 지점에서 유니온 파인드가 바로 떠올라야 한다.

풀이 흐름

1. nums를 set으로 바꿔 서로 다른 종류 수를 구한다.
2. 전체 길이의 절반만큼만 선택할 수 있다.
3. 두 값의 최솟값을 반환한다.

구현할 때 놓치기 쉬운 부분

최대로 뽑을 수 있는 개수와 서로 다른 종류 수를 따로 봐야 한다. 배열 길이만 보고 답을 만들면 안 되고, n // 2와 종류 수 중 더 작은 값을 고르는 구조라는 점이 핵심이다.

파이썬 정답 코드

def solution(nums):
  # nums를 set으로 바꿔 서로 다른 종류 수를 구한다.
  return min(len(set(nums)), len(nums) // 2)

시간 복잡도

N은 nums의 길이이다.

입력을 앞에서 뒤까지 한 번 순회하면서 비교하거나 카운트를 갱신하는 구조이다. 원소 하나를 처리할 때 붙는 비용은 상수 시간이라 전체 비용은 N번 처리 비용으로 끝난다.

따라서 시간 복잡도는 O(N)이다.