[프로그래머스] 폰켓몬 (자바)

프로그래머스 고득점 Kit: 해시 - 폰켓몬

문제 설명

당신은 폰켓몬을 최대한 많이 가지길 원합니다. 폰켓몬 종류 번호가 담긴 배열 nums가 주어졌을 때, nums의 길이의 절반을 고를 수 있는 경우 중에서 가장 많은 종류의 폰켓몬을 고르는 방법을 찾아 반환하는 문제입니다.

문제 접근 방법

1. HashSet 사용: 폰켓몬의 종류를 저장하는데 Set 자료구조를 사용하여 중복을 제거합니다.
2. 최대 폰켓몬 수 계산: 가져갈 수 있는 최대 폰켓몬 수는 nums.length / 2입니다.
3. 최종 결과 반환: Set의 크기와 최대 폰켓몬 수 중 작은 값을 반환합니다.

시간 복잡도 분석

• nums 배열의 길이를 N이라고 할 때, 시간 복잡도는 O(N)입니다.
  • 배열을 순회하며 Set에 폰켓몬 종류를 추가하는 데 O(N)

해결 방법

아래는 주어진 문제를 해결하는 Java 코드입니다:

package psg.고득점킷트.해시;

import java.util.HashSet;
import java.util.Set;

public class PSG_폰켓몬 {
    public static void main(String[] args) {
        int[] nums1 = new int[]{3, 1, 2, 3};
        int[] nums2 = new int[]{3, 3, 3, 2, 2, 4};
        int[] nums3 = new int[]{3, 3, 3, 2, 2, 2};

        PSG_폰켓몬 p = new PSG_폰켓몬();
        int answer = p.solution(nums3);
        System.out.println(answer);
    }

    public int solution(int[] nums) {
        int max = nums.length / 2; // 가져갈 수 있는 최대 폰켓몬 수
        Set<Integer> set = new HashSet<>();

        for (int num : nums) {
            set.add(num); // 중복 제거를 위해 Set에 추가
        }

        return Math.min(set.size(), max); // 중복 제거 후 폰켓몬 수와 최대 수 비교
    }
}