[프로그래머스] 폰켓몬 : Hash - L1

문제 :  폰켓몬

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

 

당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

---

 

입출력 예

[3,1,2,3]	2
[3,3,3,2,2,4]	3
[3,3,3,2,2,2]	2

---

 

풀이

나의 풀이 - HashMap 이용

import java.util.*;
class Solution {
    public int solution(int[] nums) {
        int selectSize = nums.length/2;
        int mapSize=0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int n : nums){
            if(map.get(n) == null)
                mapSize++;
            map.put(n, map.getOrDefault(n, 0)+1);
        }

        int answer = 0;
        return (selectSize > mapSize? mapSize : selectSize);
    }
}

 

더 나은 풀이 - HashSet 이용

import java.util.*;
class Solution {
    public int solution(int[] nums) {
        int selectSize = nums.length/2;
      
        HashSet<Integer> set = new HashSet<>();
        for(int n : nums){
            set.add(n);
        }
        
        return (selectSize > set.size()? set.size() : selectSize);
    }
}

 

 

HashSet

| Set 

중복이 허용되지 않는 자료구조이다. 순서 또한 보장되지 않는다.

 

HashSet의 특징

| 중복 배제

데이터 입력 시 기존 저장된 객체 중 같은 hashCode()를 찾고 만약 같으면 equals()를 통해 다시 동일 객체인지 판단 후,

동일 객체가 아닐 때만 데이터가 삽입된다.

 

즉 hashCode()가 true이고 equals()도 true일 때 => 같은 key로 처리하여 삽입 안함

자바의 hashCode란?
hashCode는 일반적으로 각 객체의 주소값을 변환하여 생성한 객체의 고유한 정수 값이다.
두 객체가 동일 객체인지 비교할 때 사용할 수 있다.

 

| value가 없는 것이 아니다.

value를 자바에서 자동으로 임의 지정한다.

 

주의. String은 hashCode가 같아도 중복 가능성이 있다.

| String의 hashCode()

String에서 재정의한 hashCode는 다음과 같다. 한 글자씩 가져와서 정수값으로 변경한다. 그렇기 때문에 문자열 같으면 서로 다른 String객체도 hashCode가 같게 되는 것이다. 때문에 원하는 결과를를 얻기 위해선 `equals()`와 `hashCode()` 함수를 재정의해줘야 한다.

public int hashCode() {
        int h = hash;
        if (h == 0 && !hashIsZero) {
            h = isLatin1() ? StringLatin1.hashCode(value)
                           : StringUTF16.hashCode(value);
            if (h == 0) {
                hashIsZero = true;
            } else {
                hash = h;
            }
        }
        return h;
    }
    
    public static int hashCode(byte[] value) {
        int h = 0;
        for (byte v : value) {
            h = 31 * h + (v & 0xff);
        }
        return h;
    }

코드에 대해 자세히 알아보면 `& 0xff` 연산을 통해  해당 바이트를 최하위 8비트로 만든 후 이전 해쉬값에 31을 곱한 후 더한다. 31을 곱하는 이유는 홀수이기 때문이다. 짝수를 곱했을 때 비트가 왼쪽으로 한 비트씩 이동되어 오버플로우가 발생하기 쉽기 때문이다. 이는 바이트 배열을 해쉬로 변환하기 위한 일반적인 해싱 기법이다.

 

해싱(hashing)

임의의 크기의 데이터를 고정된 크기의 값으로 매핑하는 과정을 말한다.
주요 목표는 빠르고 효과적으로 데이터를 검색하고 저장하는 것.

 

HashSet 요소 접근

| Iterator 사용

HashMap에 있는 keySet()이 없다. 오직 Iterator만 사용할 수 있다.

Set<String> set = ...;
Iterator<String> iterator = set.iterator();
while(set.hasNext()) {
  String str = Iterator.next();
}