[프로그래머스] lv1. 포켓몬 [#해시]

 

 

 

코테를 앞둬야만 공부하는 인생 유유

오늘은 해본지 오래된 해시를 공부해보자!

 

 

---

1. 문제 출처

---

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

프로그래머스

 

 

 

---

2. 설계 & 코드

---

 

설계1)

1) 해시맵을 쓴다.

2) for문을 돌려 nums에 있는 숫자들이 중복 제외 몇 개가 있는지 체크한다. (200001개)

3) 200001개 배열 중 1개라도 숫자가 나온 곳을 해시맵에 저장한다.

4) N/2보다 해시맵 크기가 작으면 해시맵 크기를, N/2보다 해시맵 크기가 크면 N/2를 return한다.

 

import java.util.HashMap;
class Solution {
    //다양한 종류의 포켓몬을 가질 수 있어야 한다.
    
    public int solution(int[] nums) {
        int answer = 0;
        
        int canGet = nums.length/2;//n/2만큼 포켓몬을 가질 수 있음
        
        int[] count = new int[200001];
        HashMap<Integer, Integer> realMoster = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            count[nums[i]]++;
            
            //실제 어떤 종류의 포켓몬이 있는지 확인
            if(count[nums[i]]==1){
                realMoster.put(realMoster.size()+1, nums[i]);
            }
        }
        
        if(realMoster.size()>canGet) answer = canGet;
        else answer = realMoster.size();

        
        return answer;
    }
}

 

 

설계2)

설계 1에서 배열 없이 해시맵만을 이용해서 구현해보자

중복이 있어도 업데이트해서 해시맵에 넣어줘도 포켓몬 넘버는 1개만 들어갈 것이다.

import java.util.HashMap;
class Solution {
    //다양한 종류의 포켓몬을 가질 수 있어야 한다.
    
    public int solution(int[] nums) {
        int answer = 0;
        
        int canGet = nums.length/2;//n/2만큼 포켓몬을 가질 수 있음
        
        HashMap<Integer, Integer> realMoster = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            //중복이 있어도 그냥 넣는다.
            realMoster.put(nums[i], nums[i]);
        }
        
        if(realMoster.size()>canGet) answer = canGet;
        else answer = realMoster.size();

        
        return answer;
    }
}

 

 

설계3)

근데 HashMap에 쓸모없는 value가 들어가는 것 같다. 낭비 같은데...?

 

이럴 때 쓸 수 있는 것이 HashSet이다.

- 객체를 중복해서 저장할 수 없으며, 하나의 null 값만 저장할 수 있다.

- 중복을 자동으로 제거해준다.

 

import java.util.HashSet;
class Solution {
    //다양한 종류의 포켓몬을 가질 수 있어야 한다.
    
    public int solution(int[] nums) {
        int answer = 0;
        
        int canGet = nums.length/2;//n/2만큼 포켓몬을 가질 수 있음
        
        HashSet<Integer> realMoster = new HashSet<>();
        for(int i=0;i<nums.length;i++){
            //중복이 있어도 그냥 넣는다.
            realMoster.add(nums[i]);
        }
        
        if(realMoster.size()>canGet) answer = canGet;
        else answer = realMoster.size();

        
        return answer;
    }
}

 

 

 

---

끝