[프로그래머스] 폰켓몬 (Hash)

문제 소개

오늘 풀었던 프로그래머스 - 폰켓몬 문제를 정리합니다.

이 문제는 총 N마리의 폰켓몬 중에서 N/2마리만 선택할 수 있을 때,
가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아 그때의 종류 개수의 최댓값을 구하는 문제입니다.

문제 링크: 폰켓몬 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 선택할 수 있는 폰켓몬 수는 고정 = N / 2
2. 폰켓몬의 종류 수가 이보다 많다면, 최대 N / 2 종류만 선택 가능
3. 폰켓몬의 종류 수가 이보다 적다면, 그 종류 수만큼만 선택 가능
4. 따라서 정답은 min(전체 종류 수, N / 2)

---

해결 과정 및 코드

핵심 아이디어

1. HashSet을 사용하면 중복 없이 폰켓몬의 종류 수 계산 가능
2. 이후, nums.length / 2와 set.size() 중 작은 값이 최댓값

코드

시간 복잡도 : O(N)

import java.util.*;

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