[프로그래머스 1845] 폰켓몬

• 출처: 프로그래머스 1845
• 분류: 해시 · Lv.1

문제

N마리 폰켓몬 중 N/2마리를 선택한다. 같은 종류는 같은 번호를 갖는다. 가장 많은 종류를 선택했을 때의 종류 수를 반환하라.

핵심

고를 수 있는 수는 N/2로 고정. 종류 수가 N/2 이상이면 N/2가 답이고, 미만이면 종류 수가 답이다. min(종류 수, N/2).

풀이

#include <set>
#include <vector>

using namespace std;

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

메모

• set 생성자에 iterator 범위를 넘기면 중복이 자동 제거된다. 별도 루프 필요 없음.
• kinds.size()는 size_t(unsigned)를 반환한다. nums.size() / 2도 size_t이므로 min 비교에 타입 문제가 없다.

복잡도

풀이	시간	공간
set	O(N log N)	O(N)
unordered_set	O(N)	O(N)

unordered_set을 쓰면 O(N)이지만, N이 최대 10,000이라 차이가 없다.