프로그래머스 문제 풀이 - 폰켓몬 (Java)

• 작성일: 2026-03-01

• 태그:

문제 링크

풀이 아이디어

종류가 중복되는 N마리의 폰켓몬 중에서 N/2마리를 골라, 가장 많은 종류 수를 반환하는 문제입니다.

종류 수의 최댓값을 구하는 문제이므로, 폰켓몬 종류의 중복을 제거할 필요가 있습니다.
각 종류가 몇 마리인지 기록할 필요 없이 각 포켓몬 종류 값에 대한 중복 제거만 필요하므로
Set 계열의 Collection이 적합하며, 그중에서도 삽입 및 조회의 평균 시간복잡도가 O(1)으로 빠르고
순서 유지를 위한 추가 비용이 없는 HashSet이 가장 적합합니다.
(LinkedHashSet은 순서 유지를 위한 포인터를 추가로 사용)

중복을 제거한 종류 수를 기준으로 두 가지 경우가 나뉩니다.

종류 수 ≤ N/2: 각 종류에서 한 마리씩 골라도 N/2 이내이므로, 종류 수 자체가 답입니다.
종류 수 > N/2: 종류가 아무리 많아도 고를 수 있는 수가 N/2로 제한되므로, N/2가 답입니다.

따라서 답은 min(종류 수, N/2)입니다.

정답 코드

import java.util.Set;
import java.util.HashSet;

class Solution {
    public int solution(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) set.add(num);            
        return Math.min(set.size(), nums.length / 2);
    }
}