[프로그래머스/Lv.1] 폰켓몬

1. Input

1) int 배열 nums

2) nums의 요소는 잡은 폰켓몬의 종류에 따른 번호

 

2. Output

1) N마리의 폰켓몬 중 N/2마리를 가져갈 때 가장 많은 종류의 폰켓몬을 선택하도록 방법을 찾아 그때의 폰켓몬 종류 번호의 개수를 반환

 

3. Constraint

1) nums는 폰켓몬의 종류 번호가 담긴 1차원 배열

2) nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어진다.

3) 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수

4) 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 반환하면 된다.

 

4. Example

Input: nums={3,3,3,2,2,4} -> Output: 3

- 설명: 6마리가 있으므로 3마리를 골라야 한다.

가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 1마리, 2번 1마리, 4번 1마리를 고르면 되고, 이때 고른 폰켓몬은 3종류이므로 3을 반환한다.

Input: nums={3,3,3,2,2,2} -> Output: 2

- 설명: 6마리가 있으므로 3마리를 골라야 한다.

가장 많은 종류의 폰켓몬을 고르려면 3번 2마리, 2번 1마리를 고르거나 3번 1마리, 2번 2마리를 고르면 된다. 어떠한 경우에도 2종류를 선택하므로 2를 반환한다.

 

5. Code

1) 첫 코드(2022/??)

import java.util.*;

List<Integer> list = new ArrayList();
for(int i=0 ; i<nums.length ; i++){
    if(!list.contains(nums[i]))
        list.add(nums[i]);
}

return nums.length/2 > list.size() ? list.size() : nums.length/2;

2) HashSet을 이용해본 코드(2022/11/26)

import java.util.*;

HashSet h = new HashSet();
for(int n : nums)
    h.add(n);
return nums.length/2 > h.size() ? h.size() : nums.length/2;

  - 대체적으로 2번이 1번보다 빠르다.