[C++][Programmers][해시] 포켓몬

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

프로그래머스

 

해결법

포켓몬 번호와 개수를 중복없이 저장해서 뽑는 개수대비 최대 뽑을 수 있는 개수를 구하는 문제다.

중복없이 저장해서 개수를 찾는거라 Hash의 전형적인 문제다.

Hash Map으로 값을 중복없이 저장하고 해쉬길이와 뽑을 개수의 크기를 비교해서 최소값을 출력하면 된다.

 

알아둘 것

1. C++의 foreach문

for (auto i : 배열/벡터이름)

C++11부터 지원가능 !

 

2. unordered_map

- key - value 조합으로 값을 저장하는 구조.

- 해시 테이블 형태이므로 자동 정렬되지 않아서 정렬이 필요없을 때 사용하면 좋다.

- O(1)의 검색, 삭제, 수정, 삽입의 시간 복잡도를 갖는다.

#include <iostream>
#include <unordered_map>//include
using namespace std;

int main(){
    unordered_map<string, int> map; //선언

    //데이터 삽입
    map.insert(make_pair("a", 1));
    map.insert(make_pair("b", 2));
    map.insert(make_pair("c", 3));

    //데이터 탐색
    map.find("a");
    cout << "map["a"].first: " << map["a"].first; // a
    cout << "map["a"].second: " << map["a"].second; // 1
    map.count("a");//key가 "a"인 원소의 개수 구하기
    
    //데이터 순회
    for(auto& i: map){
    	if(i.first == "b") i.second ++; // map["b"].second = 2;
    }
    
    //데이터 수정
    map["a"] = 2;
    cout << "map["a"].second: " << map["a"].second; // 2

    //데이터 삭제
    map.erase("a");
    
    //기타
    map.empty(); // 비어있으면 true, 그렇지 않다면 false를 반환
    map.size(); // map의 크기를 반환

    return 0;
}

 

3. unordered_set

- Key 데이터가 Set에 존재하는지를 판단하고 싶을 때 사용. 집합같은 느낌 !

- Map은 Key가 특정 Value에 대응되지만, Set은 Key만 가지므로 중복저장이 필요없는 Key를 저장할 때 사용한다.

- 같은 원소가 이미 들어있다면 나중에 들어오는 insert는 무시한다.

#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());
}

- 다른분이 위처럼 unordered_set으로 2줄만에 구현했길래 unordered_set도 알아두자.

 

코드

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

int solution(vector<int> nums){
    int answer = 0;
    unordered_map<int, int> pocketmons;
    
    //포켓몬 종류 추가
    for (auto num : nums){
        pocketmons.insert(make_pair(num, 0));
    }
    
    //포켓몬 개수 추가
    for (auto pocketmon : pocketmons){
        pocketmon.second++;
    }
    
    //최대 포켓몬 선택 개수 찾기
    if(pocketmons.size() > nums.size()/2){
        answer = nums.size()/2;
    }
    else if(pocketmons.size() < nums.size()/2){
        answer = pocketmons.size();
    }
    else answer = nums.size()/2;
    
    return answer;
}

직관적으로 지저분하게 짜고 다른 사람 코드보고 최적화 했다.

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

int solution(vector<int> nums){
    int answer = 0;
    unordered_map<int, int> pocketmons;
    
    //포켓몬 종류&개수 추가
    for (auto num : nums){
        pocketmons[num]++;
    }
    
    //최대 포켓몬 선택 개수 찾기
    answer = min(pocketmons.size(), nums.size()/2);
    
    return answer;
}

이건 최적화 코드. unordered_map을 구지 insert 문을 안쓰고도 값 추가가 가능하다는걸 기억해두자.