프로그래머스_폰켓몬/C++

문제

https://school.programmers.co.kr/learn/courses/30/lessons/1845

프로그래머스

여러분은 폰켓몬을 잡기 위한 오랜 여행 끝에 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 하셨습니다. 각 폰켓몬은 종류에 따라 번호가 붙어 있으며, 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 우리의 목표는 최대한 다양한 종류의 폰켓몬을 선택하는 것입니다.

- `nums = [3, 1, 2, 3]` → 결과: `2`
- `nums = [3, 3, 3, 2, 2, 4]` → 결과: `3`
- `nums = [3, 3, 3, 2, 2, 2]` → 결과: `2`

풀이

1. 중복 제거: 주어진 배열에서 중복된 폰켓몬 종류를 제거하여 고유한 종류의 수를 계산합니다.
2. 최대 선택 수 계산: N/2마리의 폰켓몬을 선택해야 하므로, 고유한 종류의 수와 N/2 중 작은 값을 선택합니다.

- **`unordered_set`**: 중복된 값을 허용하지 않는 집합 자료구조로, 폰켓몬 종류를 저장하는 데 유용합니다.
- **`for-each` 루프**: `for (int i : nums)` 구문을 사용하여 배열의 각 요소를 순회합니다.
- **`min` 함수**: 두 값 중 작은 값을 반환하는 함수로, 최종 결과를 계산하는 데 사용됩니다.

코드

(1) unordered_set 자료형을 사용해서 중복제거

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

int solution(vector<int> nums)
{
    unordered_set<int> unique_pokemon; // 중복을 제거하기 위한 집합
    for (int i : nums) {
        unique_pokemon.insert(i); // 폰켓몬 종류 추가
    }

    int maxCnt = nums.size() / 2; // 선택해야 할 폰켓몬 수
    return min(unique_pokemon.size(), maxCnt); // 고유한 종류 수와 N/2 중 작은 값 반환
}

 

(2) for each문으로 vector을 직접 순회하면서 중복제거

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

int solution(vector<int> nums)
{
    int arr[200000]; // 폰켓몬 종류를 저장할 배열 초기화
    int answer = 0; // 선택할 수 있는 폰켓몬 종류 수

    for (int i : nums) {
        if (arr[i] != 1) { // 해당 종류의 폰켓몬이 선택되지 않았다면
            answer++; // 선택 가능한 종류 수 증가
            arr[i] = 1; // 해당 종류를 선택한 것으로 표시
        }
    }
    
    int maxCnt = nums.size() / 2; // 선택해야 할 폰켓몬 수
    return min(answer, maxCnt); // 고유한 종류 수와 N/2 중 작은 값 반환
}