프로그래머스 폰켓몬 JAVA 풀이 (HashSet, 자료구조)

🔗 문제 링크

프로그래머스

 

---

📌 문제 개요

홍 박사님의 연구실에는 여러 종류의 폰켓몬이 존재한다.

전체 폰켓몬 수가 N마리일 때, 정확히 N/2마리를 선택할 수 있다.

 

이때 최대한 다양한 종류의 폰켓몬을 선택하려고 하며, 선택 가능한 폰켓몬 종류 수의 최댓값을 구하는 문제

---

📌 접근 방법

처음에는 어떤 폰켓몬을 선택해야 하는지 조합을 구해야 할 것처럼 보인다.

하지만 실제로 중요한 것은 선택한 폰켓몬의 종류 수이다.

 

따라서 HashSet을 이용하여 중복을 제거한 후 전체 종류 수를 구한다.

이후 선택 가능한 마리 수(N / 2)와 종류 수를 비교하여 더 작은 값을 반환하면 된다.

---

📌 핵심 아이디어

• HashSet으로 폰켓몬 종류를 중복 없이 저장한다.
• set.size()로 전체 종류 수를 구한다.
• 선택 가능한 폰켓몬 수는 nums.length / 2이다.
• 가질 수 있는 최대 종류 수는 두 값 중 작은 값이다.

예시)

nums = [3,3,3,2,2,4]

종류 수 = 3
선택 가능 수 = 6 / 2 = 3

정답 = 3

예시)

nums = [3,3,3,2,2,2]

종류 수 = 2
선택 가능 수 = 6 / 2 = 3

정답 = 2

 

---

📌 전체 코드

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

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);
    }
}

---

📄 정리

이 문제는 조합을 구하는 문제가 아니라 중복 제거 문제에 가깝다.

HashSet으로 종류 수를 구한 뒤, 선택 가능한 마리 수와 비교만 하면 된다.

 

문제의 조건을 단순화해서 바라보는 것이 중요한 문제였다.