[프로그래머스] 폰켓몬 unordered_set, set

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

프로그래머스

폰켓몬의 종류 번호가 담긴 배열 nums가 주어졌을 때 폰켓몬 수 N을 2로 나눈 N/2 만큼 폰켓몬을 데려갈 수 있다고 한다. 이때 최대한 다양한 종류를 데려간다고 했을 때 데려갈 수 있는 폰켓몬 종류 수를 구하는 문제이다.

(+ 예를 들어 폰켓몬이 6마리 있을 때 종류가 같은 폰켓몬이 3, 3 마리씩 이라면 최대로 데려갈 수 있는 폰켓몬의 종류의 수는 2이다.

 

나는 nums에 들어있는 폰켓몬의 종류 수를 센 다음, N/2와 비교 했을 때 더 작은 쪽을 리턴하는 방식으로 구해보았다.

int num[200005];

int solution(vector<int> nums)
{
	int numCnt = 0;	
	for (int i=0; i<nums.size(); i++)
	{
		num[nums[i]]++;
	}
	for (int i=0; i<200001; i++)
	{
		if (num[i] > 0)
			numCnt++;
	}
    return numCnt > nums.size()/2 ? nums.size()/2 : numCnt;
}

첫번째 for문 : 배열을 먼저 할당하고 그 배열에 인덱스에 따라 종류 당 폰켓몬 수를 카운트한다.

두번째 for문 : 최대 폰켓몬 종류 수(200,000) 만큼 배열을 조회하면서 nums에 있던 폰켓몬의 종류 수를 카운트 한다.

return : 폰켓몬 종류 수와 폰켓몬 수/2 중 작은 것을 반환한다.

 

다른 사람의 풀이를 봤을 때 unordered_set을 활용하여 간단하게 풀이한 코드가 있어 unordered_set에 대해 알아보기로 한다.

Unordered_set

unorderer_set 헤더에 속한 컨테이너로 set이 자동 정렬이 되는 이진트리라면, unordered_set은 정렬이 되지 않은 채로 삽입한 순서를 유지하는 이진트리라 볼 수 있다.

unordered_set은 특정한 순서 없이 unique한 원소를 저장하는 컨테이너이며, 그들의 값에 기반하여 독립적인 원소의 빠른 검색을 제공한다.

위 문제에 적용해봤을 때 폰켓몬의 종류가 들어있는 배열 nums = [3,3,3,2,2,2]라면 unordered_set은 아래와 같이 저장된다.

nums = [3, 1, 2, 3, 2, 3] 이라면 아래와 같이 나온다.

Contstructor

empty (1)	
unordered_set();explicit unordered_set ( size_type n,                         const hasher& hf = hasher(),                         const key_equal& eql = key_equal(),                         const allocator_type& alloc = allocator_type() );explicit unordered_set ( const allocator_type& alloc );         unordered_set ( size_type n, const allocator_type& alloc );         unordered_set ( size_type n, const hasher& hf, const allocator_type& alloc );
range (2)	
template <class InputIterator>  unordered_set ( InputIterator first, InputIterator last,                  size_type n = /* see below */,                  const hasher& hf = hasher(),                  const key_equal& eql = key_equal(),                  const allocator_type& alloc = allocator_type() );template <class InputIterator>  unordered_set ( InputIterator first, InputIterator last, size_type n,                  const allocator_type& alloc );template <class InputIterator>  unordered_set ( InputIterator first, InputIterator last, size_type n,                  const hasher& hf, const allocator_type& alloc );
copy (3)	
unordered_set ( const unordered_set& ust );unordered_set ( const unordered_set& ust, const allocator_type& alloc );
move (4)	
unordered_set ( unordered_set&& ust );unordered_set ( unordered_set&& ust, const allocator_type& alloc );
initializer list (5)	
unordered_set ( initializer_list<value_type> il,                size_type n = /* see below */,                const hasher& hf = hasher(),                const key_equal& eql = key_equal(),                const allocator_type& alloc = allocator_type() );unordered_set ( initializer_list<value_type> il, size_type n,                const allocator_type& alloc );unordered_set ( initializer_list<value_type> il, size_type n,                const hasher& hf, const allocator_type& alloc );

생성자는 위와 같다.

아래와 같이 선언 하여 사용할 수 있다.

std::unordered_set<std::string> first;                                // empty
std::unordered_set<std::string> second ( {"red","green","blue"} );    // init list
std::unordered_set<std::string> third ( {"orange","pink","yellow"} ); // init list
std::unordered_set<std::string> fourth ( second );                    // copy
std::unordered_set<std::string> fifth ( cmerge(third,fourth) );       // move
std::unordered_set<std::string> sixth ( fifth.begin(), fifth.end() ); // range

 

https://cplusplus.com/reference/unordered_set/unordered_set/?kw=unordered_set 

https://cplusplus.com/reference/unordered_set/unordered_set/?kw=unordered_set

 

문제에서 폰켓몬 종류의 order가 중요하지 않았기 때문에 unordered_set을 쓰든, set을 쓰든 무방하다.

set은 어떻게 선언하는지 알아보자.

 

Set

set은 set 헤더에 있으며, 특정한 순서에 따라 unique한 원소를 저장하는 컨테이너이다. 

Constructor

empty (1)	
set();explicit set (const key_compare& comp,              const allocator_type& alloc = allocator_type());explicit set (const allocator_type& alloc);
range (2)	
template <class InputIterator>  set (InputIterator first, InputIterator last,       const key_compare& comp = key_compare(),       const allocator_type& = allocator_type());template <class InputIterator>  set (InputIterator first, InputIterator last,       const allocator_type& = allocator_type());
copy (3)	
set (const set& x);set (const set& x, const allocator_type& alloc);
move (4)	
set (set&& x);set (set&& x, const allocator_type& alloc);
initializer list (5)	
set (initializer_list<value_type> il,     const key_compare& comp = key_compare(),     const allocator_type& alloc = allocator_type());set (initializer_list<value_type> il,     const allocator_type& alloc = allocator_type());

선언은 아래와 같이 할 수 있다.

std::set<int> first;                           // empty set of ints

int myints[]= {10,20,30,40,50};
std::set<int> second (myints,myints+5);        // range

std::set<int> third (second);                  // a copy of second

std::set<int> fourth (second.begin(), second.end());  // iterator ctor.

std::set<int,classcomp> fifth;                 // class as Compare

bool(*fn_pt)(int,int) = fncomp;
std::set<int,bool(*)(int,int)> sixth (fn_pt);  // function pointer as Compare

https://cplusplus.com/reference/set/set/?kw=set 

https://cplusplus.com/reference/set/set/?kw=set

 

그렇다면 이제 set과 unordered_set을 활용하여 문제를 풀어보자.

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

int solution(vector<int> nums)
{
    // set을 활용한 방식
    set<int> s(nums.begin(), nums.end());

    // unordered_set을 활용한 방식
    unordered_set<int> s(nums.begin(), nums.end());
    
    return min(s.size(), nums.size()/2);
}