[Java] 프로그래머스(level-1) - 폰켓몬

제약 사항

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

입출력 예시

Input-1
[3, 1, 2, 3]
Output-1
2

Input-2
[3, 3, 3, 2, 2, 4]
Output-2
3

문제 풀이

N개의 배열에서 N/2까지만 선택할 수 있다.
문제의 핵심은 중복되지 않는, 선택 가능한 폰켓몬의 수를 구하는 것이다.

중복을 제거하기 위해 HashSet을 활용하여 풀어보자.

HashSet이란?
Set 인터페익스에서 제공하는 구현 클래스로, 순서대로 입력되지 않고, 정렬 되지도 않으며, 중복을 허용하지 않는다.

주어진 nums배열을 HashSet에 추가하여 중복을 제거하는 코드를 작성해보자.

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

nums = [3, 3, 3, 2, 2, 4]
set = [3, 2, 4]

위와 같이 nums배열의 중복을 제거했으니 다음으로 선택 가능한 경우의 수의 최대값을 구하면 된다.

nums = [3, 1, 2, 3] 이라고 하면 중복되지 않는 2마리를 선택해야 한다.
또한 Hashset을 활용해 set = [1, 2, 3] 을 구했다.
선택할 수 있는 경우의 수의 최대값은 set의 길이에 상관없이 2마리이기에 2를 반환하면 된다.

다만, set의 길이보다 선택해야할 마리수가 많을 경우에는 선택할 수 있는 마리수가 set의 길이만큼이기에 set.size()를 반환한다.
예를 들어 nums = [1, 1, 1, 1, 1, 2, 2, 2, 2, 2]의 경우 5마리를 선택해야하고 중복이 제거된 set의 길이는 2이다.
결국 5마리를 선택하고 싶어도 선택할 수 있는 마리수는 2마리이기 때문에 set.size()인 2를 반환하면 된다.

위 내용을 코드로 작성하면 아래와 같다.

int answer = 0;
if(choice <= set.size()) answer = choice;
else answer = set.size();

작성 코드

import java.util.*;

class Solution {
    public static void main(String[] args) {
        int[] arr = {3,1,2,3};
        // int[] arr = {3,3,3,2,2,4};
        // int[] arr = {3,3,3,2,2,2};
        // int[] arr = {1,2,2,2,3,3,3,3};

        long start = System.currentTimeMillis();
        solution(arr);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }
    public static int solution(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        int choice = nums.length/2;
        for(int n : nums) set.add(n);
        
        int answer = 0;
        if(choice <= set.size()) answer = choice;
        else answer = set.size();

        return answer;
    }
}

회고

• 중복을 제거한 목록을 만들 수 있는 HashSet을 활용할 수 있었다.