[프로그래머스]폰켓몬

jh Seo·2023년 6월 12일

프로그래머스

목록 보기

3/32

개요

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
두 번째(1번), 세 번째(2번) 폰켓몬을 선택
두 번째(1번), 네 번째(3번) 폰켓몬을 선택
세 번째(2번), 네 번째(3번) 폰켓몬을 선택
이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.
당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

접근 방식

Set 이용한 방식

바로 떠오르는 방식은 set자료구조를 생성하고 모든 원소를 넣어
같은 값이면 거르는 방식이였다.
그 후, set의 크기와 벡터 num의 크기/2를 비교해서
num.size()/2보다 set의 크기가 더 크다면 num.size()/2출력 아니면
set의크기 출력하는 방식이다.

Unique()함수 이용한 방식

unique함수로 벡터를 중복제거한다는 걸 예전에 봤었어서 이용해 본 방식이다.
#include<algorithm>헤더를 인클루드해줘야한다.
그 후 , vector의 erase함수를 통해 unique가 반환하는 첫 iterator에서 end값까지 지운다.
```
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(), nums.end()),nums.end());
```
주의할 점은 unique함수는 정렬된 벡터에서만 제대로 작동한다!

Unique()함수, iterator순회 이용한 방식

위 방식에서는 erase함수에 시작 iterator과 끝 iterator을 넘겨줬지만
이번엔 직접 iterator을 순회하며 지운다.

sort(nums.begin(), nums.end());
auto iter = unique(nums.begin(), nums.end());
for (auto it = iter; it != nums.end();) {
	it = nums.erase(it);
}

주의할점은 erase함수를 실행하면 다음 iterator을 넘겨주기때문에
습관적으로 for문안에 ++it를 적었더니 segmentation fault가 떴다.

set이용한 코드

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

int solution(vector<int> nums)
{
    int totalSize = nums.size();
    set<int> s;
    int answer = 0;
    for (auto iter = nums.begin(); iter != nums.end(); ++iter) {
        s.insert(*iter);
    }
    answer = s.size()>totalSize/2 ? totalSize/2:s.size();
    return answer;
}

Unique()이용한 코드

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

int solution(vector<int> nums)
{
    int totalSize = nums.size();
    int answer = 0;
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(), nums.end()),nums.end());
 
    answer = nums.size() > totalSize / 2 ? totalSize / 2 : nums.size();
    return answer;
}

Unique()와 iterator순회 이용한 코드

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

int solution(vector<int> nums)
{
    int totalSize = nums.size();
    int answer = 0;
    sort(nums.begin(), nums.end());
    auto iter = unique(nums.begin(), nums.end());
    for (auto it = iter; it != nums.end();) {
        it = nums.erase(it);
    }
    answer = nums.size() > totalSize / 2 ? totalSize / 2 : nums.size();
    return answer;
}