[ 프로그래머스 폰켓몬 (Lv2) ] (C++)

프로그래머스의 폰켓몬(Lv2) 문제이다.

[ 문제풀이 ]

N / 2 마리의 폰켓몬을 가져올 때, 가장 많은 종류의 폰켓몬의 수를 return 해야 하는 문제이다.

본인은 폰켓몬의 종류의 수를 카운트 해주는 방식으로 문제를 해결하였다.

간단한 예시를 통해서 어떻게 해결하는지 알아보자.

예를 들어서 [ 1, 2, 3, 4 ] 가 입력으로 주어졌다고 생각해보자.

우리는 이 중에서 2마리를 가져가야 한다. 딱 봐도 알겠지만, 어떻게 2마리를 고르더라도 종류가 2종류가 가능하다.

그렇다면, [ 1, 2, 3, 4 ] 가 아닌, [ 1, 2, 3, 3 ] 으로 주어졌다고 생각해보자.

이 경우에도 딱 봐도 최대 2종류가 가능하다. 더 나아가서 [ 1, 2, 2, 2 ] 도 2종류가 가능하다.

하지만 [ 2, 2, 2, 2 ] 는 한 종류 밖에 되지 않는다.

[ 1, 2, 3, 4 ] 의 경우에는 총 '4종류'의 폰켓몬이 존재한다.

[ 1, 2, 3, 3 ] 의 경우에는 총 '3종류'의 폰켓몬이 존재한다.

[ 1, 2, 2, 2 ] 의 경우에는 총 '2종류'의 폰켓몬이 존재한다.

[ 2, 2, 2, 2 ] 의 경우에는 총 '1종류'의 폰켓몬이 존재한다.

위에서 'X종류' 라고 적어 놓은 숫자들의 의미를 한번 생각해보자. 바로 발생할 수 있는 최대 종류의 수를 나타내고 있다.

총 4 마리의 폰켓몬이 있는데...

'4종류'의 폰켓몬이 존재하는 리스트에서, 2마리를 뽑아야 하는데, 2종류의 폰켓몬을 못 뽑을까 ?? 아니다 무조건 뽑을 수 있다.

몇 개의 경우의 수만 적어본다면 [ 1, 2 ] , [ 2, 3 ], [ 3, 4 ] etc...

'3종류'의 폰켓몬이 존재하는 리스트에서, 2마리를 뽑아야 하는데, 2종류의 폰켓몬을 못 뽑을까 ?? 아니다 무조건 뽑을 수 있다.

몇 개의 경우의 수만 적어본다면 [ 1, 2 ], [ 2, 3 ], [ 1, 3 ]...

'2종류'의 폰켓몬이 존재하는 리스트에서, 2마리를 뽑아야 하는데, 2종류의 폰켓몬을 못 뽑을까 ?? 아니다 무조건 뽑을 수 있다.

그 경우는 [ 1 , 2 ]

'1종류'의 폰켓몬이 존재하는 리스트에서, 2마리를 뽑아야 하는데, 2종류의 폰켓못을 못 뽑을까 ?? 그렇다 절대 뽑을 수가 없다.

[ 1... ?? ] 뽑을 수가 없다 !

N 마리가 주어졌을 때, 그 N마리가 총 'X종류'로 이루어져 있다고 표현해보자. 우리는 이 중에서 N / 2 마리를 뽑아야 한다.

이 때 ! X >= N / 2 이면, 무조건 N / 2종류를 뽑을 수 있다는 것을 의미한다.

반대로, X < N / 2 이면, 무조건 X종류를 뽑을 수 있다는 것을 의미한다.

따라서, 정말 간단하게 주어진 리스트에 존재하는 '종류의 수'를 Count해준 후에, N / 2 한 값과 비교를 해서 더 작은 값이

정답이 된다.

[ 소스코드 ]

#include<vector>
using namespace std;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
int solution(vector<int> nums)
{
    int N = nums.size() / 2;
    int Cnt = 0;
    bool Visit[200010] = { false, };
    for (int i = 0; i < nums.size(); i++)
    {
        int Num = nums[i];
        if (Visit[Num] == false)
        {
            Visit[Num] = true;
            Cnt++;
        }
    }
 
    int answer = Min(N, Cnt);
    return answer;
}