프로그래머스 1845 폰켓몬 (C++)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/1845

 

문제 요약

전체 폰켓몬 N 마리 중, N/2 마리를 골랐을 때, 가질 수 있는 가장 많은 종류의 값을 구하는 문제입니다.

풀이

전체 폰켓몬 N/2 마리 중 가장 많은 종류의 폰켓몬을 고르는 것이므로 종류의 최대값은 N/2을 넘을 수 없습니다(고른 N/2 마리가 전부 다른 종류일 경우가 가장 많이 고른 것임).

그리고 전체 폰켓몬의 종류의 수를 X라고 했을때 X가 N/2보다 작다면, 고를 수 있는 종류의 최대값은 X를 넘을 수 없습니다(아무리 잘 골라도 전체 폰켓몬 종류보다 많은 종류를 고를 수 없음).

 

따라서, 전체 폰켓몬 종류 수 X를 구한 후, X와 N/2 중 더 작은 값이 -> N/2 마리를 골랐을 때 가질 수 있는 가장 많은 종류의 값입니다.

 

set 자료구조에 폰켓몬을 담으면 중복이 제거되므로 set.size()로 간단하게 종류 수를 구할 수 있습니다.

set은 레드블랙트리 기반이라 삽입 평균 시간복잡도가 O(logN) 입니다. Hash table 기반의 unordered_set을 사용하면 평균 시간복잡도가 O(1) 이므로 더 효율적입니다.

 

코드

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

int solution(vector<int> nums)
{
    unordered_set<int> kinds(nums.begin(), nums.end());
    return min(kinds.size(), nums.size() /2);
}