프로그래머스 코딩테스트 연습 - 폰켓몬 (Level 1)

programmers

 

문제

프로그래머스 코딩테스트 연습 - 폰켓몬 (Level 1)

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

코딩테스트 연습 - 폰켓몬

---

사용 알고리즘

- 해시

 

풀이

폰켓몬의 종류를 중복없이 모두 센 다음

그 개수와 n/2 중 더 작은 값을 반환하면 된다.

 

나의 코드

#include <vector>
#include <algorithm>
using namespace std;
bool mon[200001];

int solution(vector<int> nums)
{
    int answer = 0;
    for(auto i:nums){
        if(!mon[i]){
            mon[i]=true;
            answer++;
        }
    }
    if(answer>nums.size()/2)
        answer=nums.size()/2;
    return answer;
}

 

남의 코드(좋아요 최다 코드)

#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<int> nums)
{
    unordered_map<int, int> hash;

    for (auto num: nums) {
        hash[num] += 1;
    }

    return min(hash.size(), nums.size() / 2);

}

 

unordered_map을 쓰면 공간복잡도가 크게 단축된다.

다음부턴 써야겠다...

쓰는 걸 깜박함.