[C++] Programmers Lv. 1 "폰켓몬"

🔵 문제 링크

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

프로그래머스

 

🔵 문제 접근

중복을 배제해 놓으면 쉽게 풀 수 있는 문제이다.

unordered_set으로 중복을 제거한 후 뽑아야 하는 폰켓몬 수, 중복을 제거한 폰켓몬 종류 수 중 적은 값을 택하면 뽑을 수 있는 최대 종류의 수이다.

 

🔵 전체 코드

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

// 가장 많은 종류의 폰켓몬을 갖고 싶다.
// unordered_set으로 중복을 제거한다.
// min(뽑아야 하는 폰켓몬 수 (n / 2), unordered_set.size())

int solution(vector<int> nums)
{
    unordered_set<int> ponketmon(nums.begin(), nums.end());

    return min((int)nums.size() / 2, (int)ponketmon.size());
}

 

🔵 시간 복잡도

nums을 unordered_set으로 변환할 때 시간 복잡도는 nums의 길이를 N이라 할 때, O(N)이다.