프로그래머스 - 폰켓몬

문제 출처

문제 출처 : 폰켓몬

문제 이해하기

• 지금까지 풀었던 문제들 중 지문이 조금 긴 문제이다. 하지만 잘 읽어보면 어렵지 않게 풀 수 있다.
• 연구실에 있는 N마리의 폰켓몬 중 N/2 마리를 가져갈 수 있는데, 이때 종류에 중복되지 않고 최대한으로 가져갈 수 있는 폰켓몬의 수를 구하면 된다.

주요 조건 이해하기 ⭐️

문제를 잘 읽어보면 N마리의 폰켓몬 중 N/2 마리를 가져갈 수 있다는 문장이 있다. 그 말은 중복없이 폰켓몬 종류가 다양하다고 해도, 결국 N/2 마리를 가져갈 수 밖에 없다는 이야기이다.

최대 가져갈 수 있는 폰켓몬의 수 : N/2

입출력으로 주어진 예시들을 머릿속으로 직접 시뮬레이션을 한다면 아래와 같다.

[3, 1, 2, 3] -> 최대 2마리, 서로 다른 종류는 3마리 (3, 1, 2)

[3, 3, 3, 2, 2, 4] -> 최대 3마리, 서로 다른 종류는 3마리 (3, 2, 4)

[3, 3, 3, 2, 2, 2] -> 최대 3마리, 서로 다른 종류는 2마리 (3, 2)

//이 예시는 이해를 위해 만든 예시
[3, 3, 3, 3, 2, 2, 2, 2] -> 최대 4마리, 서로 다른 종류는 2마리 (3, 2)

이러한 관찰을 통해 아래와 같은 순서로 코드를 작성할 수 있다.

1. 서로 다른 종류의 폰켓몬을 1마리씩 구해보기 위해 입력으로 들어온 폰켓몬에서 중복된 종류를 제거한다.
2. 1번에서 구한 폰켓몬의 마릿수가 N/2보다 많으면 N/2값을 반환하고, 만약 적다면 폰켓몬의 마릿수를 반환하면 된다.

그렇다면 중복된 종류들을 어떤 방법으로 제거할 수 있을까?
친절하게도 문제의 종류가 '해시'라는 것을 눈치챘다면 자바의 HashSet을 이용해서 풀 수 있을 것이다.

Set은 중복없이 원소들을 보관할 수 있는 Collection 자료형이다.

이를 바탕으로 제출 코드를 작성해보면 아래와 같이 작성할 수 있다.

제출 코드

import java.util.*;

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

		HashSet<Integer> set = new HashSet<>();

		for (int num : nums) {
			set.add(num);
		}

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