[프로그래머스] 폰켓몬

1. 문제

---

프로그래머스

 

2. 풀이 과정

---

N/2마리의 폰켓몬을 선택할 때 최대 몇 종류의 폰켓몬을 선택할 수 있는지를 계산하는 문제이다.

 

해결하는 과정은 다음과 같다.

 

1. N마리의 폰켓몬 중 중복을 제거한다.

최대 몇 종류인지를 알아야하기 때문에 중복된 폰켓몬은 제거해줘야 한다. 

nums 배열을 순회하며 해시 셋에 데이터를 넣어 중복을 제거해준다.

 

2. 중복이 제거된 폰켓몬 목록을 통해 최대 몇종류의 폰켓몬을 선택할 수 있는지 파악한다.

폰켓몬은 최대 N/2 마리까지 선택할 수 있고 그 N/2 마리는 최대한 다른 종류의 폰켓몬을 선택해야한다.

그렇게 하기 위해선 1에서 구한 해시 셋의 크기만큼 폰켓몬을 선택해야 한다. 

결론적으로 1에서 구한 해시 셋의 크기가 N/2보다 크다면 정답은 N/2가 되고 만약 반대로 작다면 정답은 해시 셋의 크기가 된다.

 

매우 간단한 문제이다. 

이제 코드를 보자. 

3. 내 코드

---

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

시간 복잡도

• O(N)