[프로그래머스] 폰켓몬 (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);
}