본문 바로가기
알고리즘 문제풀이

[프로그래머스] 폰켓몬 (C++)

by SiO2whocode 2024. 10. 31.
728x90

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

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

Hash 해시

폰켓몬 - [3,3,3,2,2,4] 이렇게 n개의 포켓몬?에 대해 포켓몬종 번호가 주어짐, 이중 n/2(n은 늘 짝수)개를 뽑는데, 가능한 다양한 종을 뽑을 때, 최대로 뽑을 수 있는 종의 수를 구하는 문제 

 

접근방법

- 포켓몬종 : 수 - 형식의 map을 만든다.

- 그러면 최소 1개는 있는 종들로 map이 만들어짐 (즉, 없는 종은 아예 맵에 데이터가 만들어지지 않음) = map의 크기가 최대로 뽑을 수 있는 종의 수

- 이 존재하는 최대 종의 갯수와 뽑을 수 있는 포켓몬의 수 (n/2) 를 비교해서 뽑을 수 있는 포켓몬 수(n/2)보다 존재하는 종의 수가 더 많다면 n/2개 밖에 못뽑는거고(더 다양한 종을 뽑고 싶어도 못뽑음), 내가 뽑을 수 있는 포켓몬 수 보다 존재하는 종의 수가 더 작으면 존재하는 만큼만 갖는거다.

전자를 max라고 하면,

- max >= n/2 : n/2

- max < n/2 : max

 

오답노트

오답은 아니었고,,다른 사람들 코드 보는데 너무 간결하게 잘 해서

난 원래 map의 size가 존재하는 최대 종의 수라는 생각을 못하고, map 원소들 다 보면서 하나씩 포켓에 담듯이 세다가 n/2넘으면 n/2에서 멈추는 식으로 했었는데 두 값을 비교하는 걸로 고쳤다.

 

+ c++ map은 추가하지 않아도 새로 key값 조회하면 (ex. map[0] // 0으로 출력) 0이 기본값으로 출력된다. 그렇다고 내가 값을 넣어주거나 초기화해주지 않으면 map에 size에 포함되지는 않음.

+ map<int, int> 이런식으로 만들면 map 원소 하나에 접근해서 Key랑 value 조회하려면, .first, .second해야한다. (원소 순회하는건 auto a : map 이런식으로 했다.

 

소스코드

#include <vector>
#include <map>
#include <iostream>
using namespace std;

int solution(vector<int> nums)
{
    int answer = 0;
    map<int, int> m;
    
    for(int i = 0 ; i < nums.size() ; i++){
        m[nums[i]]++;
    }
    
    answer = (m.size() > nums.size()/2 ? nums.size()/2 : m.size());
    return answer;
}

 

728x90