[프로그래머스/c++] 폰켓몬

성공 코드(내 코드)

선택해야 하는 폰켓몬의 마리 수 = nums의 사이즈/2

위의 값을 미리 저장해두고

폰켓몬의 종류 번호가 담긴 1차원 배열 nums의 중복 원소를 제거한다.

 

unique는 연속된 중복 원소를 vector의 제일 뒷부분으로 쓰레기값으로 보낸다.
따라서 sort 함수로 vector를 정렬한 뒤 unique 해줘야 한다.
unique시 반환 되는 값은 vector의 쓰레기값의 첫번째 위치이다.
이를 이용하여 unique 후 erase가 가능하다.

 

nums에는 폰켓몬의 종류만 남게 된다.

 

구하고자 하는 것은 다음과 같다.

가장 많은 종류의 폰켓몬을 선택하는 방법에서 폰켓몬 종류 번호의 개수

• 선택해야 하는 폰켓몬의 마리 수 >= 폰켓몬의 종류
  • 폰켓몬의 종류
• 선택해야 하는 폰켓몬의 마리 수 < 폰켓몬의 종류
  • 선택해야 하는 폰켓몬의 마리 수

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

int solution(vector<int> nums)
{
    int answer = nums.size()/2;
    
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    if(nums.size()<=answer){
        return nums.size();
    }
    
    return answer;
}

 

---

다른 사람 풀이

set을 이용

• key라고 불리는 원소들의 집합으로 이루어진 컨테이너
• 원소가 key
• key값의 중복이 허용되지 않는다.

#include <bits/stdc++.h>
using namespace std;

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

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

 

map을 이용

• 각 노드가 key와 value 쌍으로 이루어진 트리
• pair 객체로 저장되며 first-key로 second-value로 저장된다.
• 중복을 허용하지 않는다.

#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<int> nums)
{
    unordered_map<int, int> hash;

    for (auto num: nums) {
        hash[num] += 1;
    }

    return min(hash.size(), nums.size() / 2);

}