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

https://programmers.co.kr/learn/courses/30/lessons/1845?language=cpp 

코딩테스트 연습 - 폰켓몬

---

1) 풀이

폰켓몬 N/2 마리를 최대한 많은 종류로 선택하는 방법은,

주어지는 폰켓몬 배열에서 중복값을 제거하고 고르는 방법이다.

중복값을 제거하는 방법은 unique 함수를 이용하면 된다.

해당 함수로 중복값을 제거하는 방법은 아래 글에 정리해놓았다!

2021.06.16 - [언어/c++] - [c++] vector 중복원소 제거(sort, unique)

 

중복값을 제거한 후에, N/2 마리를 골랐을 때 최대로 선택할 수 있는 종류 수를 정답변수로 넣어주면 된다.

(N은 중복값을 제거하기 전에 맨 처음 주어진 배열의 크기를 의미한다)

 

만약 중복값을 제거한 후의 배열의 크기가 N/2보다 크거나 같다면 최대 N/2 종류만큼 고를 수 있다는 의미이고,

중복값을 제거한 후의 배열의 크기가 N/2보다 작다면 N/2 마리를 선택할 수 있어도 중복되는 종류를 반드시

골라야한다는 의미이므로, 중복값을 제거한 후의 배열 크기만큼의 종류를 최대로 고를 수 있다.

2) 최종 소스코드

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

int solution(vector<int> nums)
{
    int answer = 0;
    int s=nums.size()/2; //N/2마리를 뽑아야 하므로, 중복값 제거 전에 미리 변수로 저장
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    
    if(s<=nums.size()){
        answer=s;
    }
    else answer=nums.size();
    return answer;
}

3) 참고자료