[프로그래머스] 폰켓몬 (Lv.1)


문제 링크


프로그래머스 - 폰켓몬


문제 설명


당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 드디어 폰켓몬 마을에 도착했습니다. 이 마을에서 폰켓몬을 구매할 수 있는데, 여러 종류의 폰켓몬이 있습니다. 마을의 폰켓몬 박사는 여러분에게 n/2마리의 폰켓몬을 선택하라고 합니다. 단, 최대한 다양한 종류의 폰켓몬을 가져가길 원합니다.

당신은 최대 몇 종류의 폰켓몬을 선택할 수 있는지를 return 하도록 solution 함수를 완성해 주세요.

제한사항

  • nums의 길이(n)는 1 이상 10,000 이하의 자연수이며, 항상 짝수입니다.
  • 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수입니다.
  • 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.


내 풀이


nums를 unordered_set에 삽입해 고유한 종류 수를 구한다. 선택할 수 있는 마리 수는 n/2이고, 최대한 다양하게 고르려면 min(고유 종류 수, n/2)가 답이다. 고유 종류가 충분히 많으면 n/2종을 전부 다르게 선택할 수 있고, 부족하면 있는 종류만큼만 선택할 수 있다.

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

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


시간복잡도 분석


  • nums 순회 (set 삽입): O(n) 평균
  • 전체: O(n)

n ≤ 10,000이므로 충분히 통과 가능하다.


후기


코드를 이렇게 압축할 수도 있는 것 같다. 잘 기억해둬야겠다.

#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

int solution(vector<int> nums)
{
    unordered_set<int> s(nums.begin(), nums.end());
    return min(s.size(), nums.size() / 2);
}