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

폰켓몬

문제 링크

폰켓몬

분석

해당 문제의 상황은 N마리의 폰켓몬 중 절반만큼만 폰켓몬을 가져가고자 합니다.
그런데 폰켓몬을 최대한 다양하게 가져가려 한다는 조건이 붙어있습니다.
그렇기 때문에 최대한 서로 다른 종류를 선택 할 때 얼만큼 많은 종류의 개수를 가져갈 수 있는지 구해야합니다.

입력으로는 종류 번호가 담긴 1차원 배열이 주어집니다.
해당 배열은 짝수의 크기를 가지기 때문에 크기가 홀수 일 경우를 신경쓰지 않아도 되고, 배열의 요소는 int로 표현할 수 있는 자연수입니다.

우선 종류의 개수만 알면 되기 때문에 중복된 값은 제거할 필요가 있습니다.
여기서 중복을 제외하고 남은 배열의 크기가 최대한 다양하게 가져갈 수 있는 크기가 됩니다.

만약 종류의 수가 N의 절반보다 크거나 같을 경우 중복돼서 담길 일이 없기 때문에 최대값은 N/2, 반대로 N의 절반보다 작을 경우 선택 개수를 채우기 위해 같은 값이 중복돼야하기 때문에 최대값은 종류의 수가 됩니다.

결과적으로 서로 다른 종류의 개수와 선택 가능한 개수인 N/2 중 더 작은 값이 반환값이 됩니다.

풀이

#include <vector>
#include <unordered_set>

using namespace std;

int solution(vector<int> nums)
{
    int answer = nums.size() / 2;
    
    unordered_set<int> numSet;
    
    for (int num : nums)
    {
        numSet.insert(num);
    }
    
    if (numSet.size() < nums.size() / 2)
    {
        answer = numSet.size();
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(N)$입니다.

• nums를 순회하며 unordered_set에 값 삽입 $O(N)$

공간 복잡도는 $O(N)$입니다.

• nums의 모든 값이 다를 경우 unordered_set $O(N)$

테스트 성능

정확성 테스트

테스트 1 〉통과 (0.01ms, 3.63MB)
테스트 2 〉통과 (0.01ms, 4.14MB)
테스트 3 〉통과 (0.01ms, 4.21MB)
테스트 4 〉통과 (0.01ms, 4.14MB)
테스트 5 〉통과 (0.01ms, 3.68MB)
테스트 6 〉통과 (0.01ms, 3.68MB)
테스트 7 〉통과 (0.02ms, 4.17MB)
테스트 8 〉통과 (0.02ms, 4.02MB)
테스트 9 〉통과 (0.01ms, 3.63MB)
테스트 10 〉통과 (0.01ms, 4.15MB)
테스트 11 〉통과 (0.01ms, 4.22MB)
테스트 12 〉통과 (0.12ms, 4.22MB)
테스트 13 〉통과 (0.08ms, 4.15MB)
테스트 14 〉통과 (0.08ms, 4.23MB)
테스트 15 〉통과 (0.04ms, 4.15MB)
테스트 16 〉통과 (0.71ms, 4.21MB)
테스트 17 〉통과 (0.71ms, 4.15MB)
테스트 18 〉통과 (0.45ms, 4.14MB)
테스트 19 〉통과 (0.29ms, 4.21MB)
테스트 20 〉통과 (0.18ms, 4.18MB)