문제

Programmers 폰켄몬

핵심

• 입력의 크기가 $10^4$이라 대략 $O(N^2)$ 이하의 알고리즘을 사용한다.
• 최대한 다양한 포켓몬을 선택하는 게 목표이므로, 포켓몬을 hash 자료구조에 담아 중복을 제거하여 N/2마리를 선택한다.
• C++은 unordered_set, Java는 HashSet을 사용한다.

개선

halfSize만큼 해시 자료구조에 저장해도 되지만, halfSize와 해시 자료구조 크기의 최소값으로 답을 결정할 수 있다.

코드

시간복잡도

• $O(N)$

C++

#include <vector>
#include <iostream>
#include <unordered_set>
using namespace std;

int solution(vector<int> nums)
{
    unordered_set<int> s;
    int halfSize = nums.size() / 2;
    for (auto n : nums) {
        if (s.size() >= halfSize)
            break;
        s.insert(n);
    }
    int answer = s.size();
    return answer;
}

Java

import java.util.*;
class Solution {
    public int solution(int[] nums) {
        int halfSize = nums.length / 2;
        HashSet<Integer> hs = new HashSet<>();
        for (var n : nums) {
            if (hs.size() >= halfSize)
                break;
            hs.add(n);
        }
        int answer = hs.size();
        return answer;
    }
}