[Java] 프로그래머스 - 폰켓몬

중복을 제거해 폰켓몬 종류 수를 구한 뒤, 고를 수 있는 마리 수(N/2)와 비교해서 더 작은 값을 반환하는 문제.

 

1. 문제 유형

해시

 

2. 내가 놓친 포인트

처음 떠올린 접근 : 전체 폰켓몬 수의 절반만 선택 가능하니까 nums.length / 2를 먼저 구하고 HashSet을 통해 중복을 제거해서 둘 중 더 작은 값을 반환하려고 했다.

오답 원인: 중복 제거를 위해 HashSet을 써야 하는 건 맞았는데, HashMap처럼 제네릭을 두 개 넣어버렸다.

 

3. 핵심 로직 & 해결 방법

핵심 조건: N마리 중 정확히 N/2마리만 선택 가능하고 최대한 많은 종류를 골라야한다.

풀이 아이디어:

1. nums.length / 2로 선택 가능한 마리 수를 구한다.
2. HashSet에 배열의 값을 전부 넣어 중복을 제거하고 종류 수를 구한다.
3. 선택 가능한 수와 종류 수를 비교해서 더 작은 값을 반환한다.

4. 구현 코드

import java.util.HashSet;

class Solution {
    public int solution(int[] nums) {
        int pick = nums.length / 2;

        HashSet<Integer> set = new HashSet<>();
        for (int n : nums) {
            set.add(n);
        }

        return pick > set.size() ? set.size() : pick;
    }
}

시간 복잡도: O(N) / 공간 복잡도: O(N)

---

 

인사이트

• HashSet은 중복 제거, HashMap은 개수 세기 / key-value 저장 용도라는 차이를 다시 정리할 수 있었다.

 

문제 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/1845