Programmers / Level 1 / 폰켓몬

[문제설명]

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

[제한사항]

• nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
• nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
• 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
• 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다

[입출력 예]

nums	result
[3,1,2,3]	2
[3,3,3,2,2,4]	3
[3,3,3,2,2,2]	2

 

내가 작성한 코드

import java.util.ArrayList;

class Solution {
    public int solution(int[] nums) {
        int answer = 0; // 폰켓몬 종류의 수
        int num = nums.length/2; // 얻을 수 있는 폰켓몬 수
        
        ArrayList<Integer> list = new ArrayList<>(); // 얻은 폰켓몬 넣을 배열
        for (int i = 0; i < nums.length; i++) {
            if (num == 0)
                break;
            
            if (list.contains(nums[i])) {
                continue;
            }
            list.add(nums[i]);
            num--;
            answer++;
        }

        return answer;
    }
}

 

우선, 내가 얻을 수 있는 폰켓몬의 수는 홍 박사가 갖고있는 총 N마리 (nums배열의 길이)의 1/2이다.

이를 나타내는 num 변수를 새로 생성했다.

 

내가 얻은 폰켓몬을 넣을 ArrayList를 생성했고,

for문을 돌며 폰켓몬을 ArrayList에 넣는다.

 

단, 

기존에 가지고 있던 폰켓몬 종류와 같다면 추가하지 않는다. 또한, num변수가 0이 되면 (얻을 수 있는 폰켓몬 수 0) for문을 빠져나오게 했다.

ArrayList에 폰켓몬을 넣을 때 폰켓몬 종류의 수를 나타내는 answer에 +1 해주기 때문에 결국, 내가 얻을 폰켓몬 종류의 수를 얻을 수 있게 된다.

 

---

 

생각했던 것 보다 비교적 간단하게 풀렸지만, 더 좋은 방법이 있을 듯 싶어 다른 사람들의 코드도 찾아봤다.

중복 제거를 하는 방법이 가장 많이 보였다.

ArrayList를 사용하는 방법도 있었지만, HashSet을 사용하는 것이 더 간단해보였다. HashSet은 사용해본적이 없어 구글링을 하며 공부하고 정리해봤다.

 

아래는 HashSet을 이용해 중복 제거를 한 후, 작성해본 코드이다.

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int answer = 0; // 폰켓몬 종류의 수
        int num = nums.length / 2; // 얻을 수 있는 폰켓몬 수

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

        if(hash.size() > num) { // 중복 제거한 배열 수가 더 큰 경우
            answer = num;
        }
        else {
            answer = hash.size();
        }
        return answer;
    }
}

HashSet 관련 포스팅 : https://gr616.tistory.com/244