프로그래머스 포켓몬

프로그래머스 포켓몬

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

프로그래머스

Level 1 문제라 그런지 문제를 처음 봤을 때 생각보다 간단하게 구현이 가능할 거라고 생각했다.

내가 생각한 알고리즘은 다음과 같다.

1. 새로운 벡터 v를 만듭니다.
2. 함수에서 받아온 nums 배열의 값을 백터v의 인덱스로 사용하였다.
3. 해당 인덱스를 1씩 증가시키도록 설정하였다.
4. 그리고 0이 아닌 값을 가진 인덱스만 찾아, count를 증가시키는 반복문을 통해 백터v를 처리하였다.
5. count는 문제에서 제시된 가장 다양한 종류의 포켓몬을 선택하는 방법이었다.
6. 문제의 요구사항은 N/2마리의 포켓몬 중에서 가장 다양한 종류를 선택하고, 그때의 포켓몬 종류 번호의 개수를 반환하는 solution 함수를 완성하는 것이었다.
7. 따라서, count가 N/2보다 작은 경우에만 answer에 count 값을 할당하여 문제를 해결하였다.

코드

#include <vector>
using namespace std;

int solution(vector<int> nums)
{
    int answer = 0;
    int count=0;
    answer = nums.size()/2;
    vector<int>v(200000);
    
    for(int i=0;i<nums.size();i++){
        v[nums[i]]++;
    }
    
    for(int i=0; i<v.size();i++){
        if(v[i]!=0){
            count++;
        }
    }
    
    if(count<nums.size()/2)
        answer = count;
    
    return answer;
}

한번에 성공하고 다른 사람의 풀이가 궁금해서 찾아 보았는데 진짜 말도 안되게 짧은 코드를 보았다.

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> nums) {
    unordered_set<int> s(nums.begin(), nums.end());

    return min(nums.size() / 2, s.size());
}

아직 cpp이 어리숙해서 unordered_set이 함수가 낯설다.

대체 뭐하는 놈인지 찾아보았다.

C++ 표준 라이브러리(STL)에는 여러 가지 컨테이너가 있다. unordered_set을 찾아보니 unordered_map라는 애도 항상 같이 나와서 둘이 어떤 차이점이 있는지 알아보았다.

unordered_set은 집합(set)을 구현한 STL 컨테이너로, 중복된 원소를 저장하지 않는 특성을 가진다. 반면에 unordered_map은 키와 값의 쌍을 저장하는 컨테이너이다. 따라서 주어진 문제에 대한 솔루션에서는 unordered_set을 사용하여 중복 없이 폰켓몬의 종류를 저장한 후, 저장된 폰켓몬 종류의 개수와 N/2 중 작은 값을 반환하여 문제를 해결했던 것이다.

unordered_set

unordered_set은 C++의 표준 라이브러리인 STL (Standard Template Library)에 포함된 컨테이너 중 하나이다. 이는 해시 테이블 기반의 집합(Set)을 구현한다.

간단히 말하면, unordered_set은 유일한(unique)한 요소들의 모임을 저장하는 자료구조이다. 그러나 set과는 다르게 요소들이 정렬되지 않는다. 요소들은 해시 함수를 사용하여 저장되므로, 삽입, 삭제, 검색 등의 연산이 평균적으로 매우 빠르다.

unordered_set을 사용하려면 <unordered_set> 헤더 파일을 포함해야 합니다. 일반적으로 해시 테이블의 크기를 조절하는 것과 해시 함수를 지정하는 것이 가능하다.

unordered_set을 사용하는 방법이다.

cppCopy code
#include <iostream>#include <unordered_set>int main() {
    // unordered_set 생성
    std::unordered_set<int> mySet;

    // 요소 삽입
    mySet.insert(10);
    mySet.insert(20);
    mySet.insert(30);

    // 중복된 요소는 삽입되지 않음
    mySet.insert(10);

    // 요소 삭제
    mySet.erase(20);

    // 요소 존재 여부 확인
    if (mySet.find(10) != mySet.end()) {
        std::cout << "10 is present in the set\\n";
    }

    // 요소 순회
    for (int x : mySet) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

이 예제에서는 **unordered_set**을 생성하고, 요소를 추가하고 삭제하며, 요소의 존재 여부를 확인하고, 요소를 순회하고 출력하는 방법을 보여준다. unordered_set은 삽입, 삭제, 검색 연산이 빠르기 때문에 대규모 데이터를 다룰 때 유용하게 사용된다.

unordered_map

unordered_map은 C++의 표준 라이브러리인 STL (Standard Template Library)에 포함된 컨테이너 중 하나이다. 이는 해시 테이블 기반의 맵(Map)을 구현한다.

unordered_map은 키-값 쌍을 저장하는 자료구조이며, 키는 유일해야 하지만 값은 중복될 수 있다. unordered_map은 해시 함수를 사용하여 키를 해시 값으로 변환하고, 이를 이용하여 키-값 쌍을 저장하므로, 삽입, 삭제, 검색 등의 연산이 평균적으로 매우 빠르다.

unordered_map을 사용하려면 <unordered_map> 헤더 파일을 포함해야 한다. 일반적으로 해시 테이블의 크기를 조절하는 것과 해시 함수를 지정하는 것이 가능하다.

unordered_map을 사용하는 방법이다.

cppCopy code
#include <iostream>#include <unordered_map>int main() {
    // unordered_map 생성
    std::unordered_map<std::string, int> myMap;

    // 요소 삽입
    myMap["apple"] = 3;
    myMap["banana"] = 5;
    myMap["orange"] = 2;

    // 중복된 키의 경우 값이 갱신됨
    myMap["apple"] = 10;

    // 요소 삭제
    myMap.erase("banana");

    // 요소 존재 여부 확인
    if (myMap.find("orange") != myMap.end()) {
        std::cout << "The value associated with 'orange' is: " << myMap["orange"] << std::endl;
    }

    // 요소 순회
    for (const auto& pair : myMap) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
    }

    return 0;
}

이 예제에서는 **unordered_map**을 생성하고, 요소를 추가하고 삭제하며, 요소의 존재 여부를 확인하고, 요소를 순회하고 출력하는 방법을 보여준다.unordered_map은 키-값 쌍을 효율적으로 관리할 수 있으며, 대용량 데이터를 다룰 때 유용하게 사용된다.

unordered_set과 unordered_map의 주요 차이점은 다음과 같다.

1. 저장하는 요소의 종류:
   • unordered_set: 유일한(unique)한 요소들의 집합을 저장한다. 요소들은 정렬되지 않는다.
   • unordered_map: 키-값 쌍을 저장한다. 각 키는 유일해야 하지만, 값은 중복될 수 있다.
2. 구조:
   • unordered_set은 단순히 값만을 저장한다.
   • unordered_map은 키-값 쌍을 저장한다.
3. 사용 시점:
   • unordered_set은 단순히 값의 존재 여부를 확인하거나 중복된 값의 저장 여부를 확인할 때 사용된다.
   • unordered_map은 키와 값을 매핑하고, 키를 기반으로 값을 검색, 삽입, 삭제할 때 사용된다.
4. 구조적인 활용:
   • unordered_set은 주로 중복을 허용하지 않는 집합을 다룰 때 유용하다. 예를 들어, 고유한 ID나 값의 존재 여부를 확인할 때 사용된다.
   • unordered_map은 키-값 쌍을 관리할 때 유용하다. 예를 들어, 단어의 빈도수를 세거나 특정 키워드에 대한 연관 정보를 관리할 때 사용된다.

요약하자면, unordered_set은 유일한 값들을 저장하고 관리하는 데 사용되고, unordered_map은 키와 값을 매핑하여 데이터를 저장하고 관리하는 데 사용된다. 이러한 차이로 인해 각각의 컨테이너는 다른 상황에서 사용된다.