해쉬) 프로그래머스 : 완주하지 못한 선수 / 폰켓몬

1. 완주하지 못한 선수

• 문제 접근 : 참가 명단과 완주 명단을 비교하는 것이므로, 선수 이름을 대조하기 위하여 명단을 저장하는 자료구조로 해쉬를 사용한다. 이 때, Key는 이름, Value는 인원 수이다. 이름이 중복될 수 있기 때문에 Value 가 필요하다. 참가 명단과 완주 명단을 저장한 각각의 해쉬 맵을 비교하며 차이나는 한 명을 반환한다.
  
  • for문을 통해 해쉬 맵의 요소를 탐색하면서 값이 1인 이름을 반환한다. 이 때, 해쉬를 순회하기 위해서는 인덱스를 통한 접근이 불가능하므로, hashMap의 keySet()(Key가 저장된 Set을 반환)이나 entrySet()(Key-Value 구조인 엔트리가 저장된 Set을 반환)을 사용한다.

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        Map<String, Integer> hMap = new HashMap<>();
        for(String str : participant) hMap.put(str,hMap.getOrDefault(str, 0) + 1);
        for(String str : completion) hMap.put(str, hMap.get(str)-1);
        
        for(Map.Entry<String, Integer> entry : hMap.entrySet()){
            if(entry.getValue() == 1){
                return entry.getKey();
            }
        }
        return answer;
    }
}

• getOrDefault는 해쉬 맵의 메서드로, Key에 대한 Value를 get 하되, 없을 경우 Default 값을 반환하는 메서드이다.
• keySet을 사용할 경우, for문 내부에서 다시 한번 get()을 통해 Key에 대한 값을 가져오는 연산이 진행된다. 따라서 Key와 Value 모두를 가져오는 entrySet() 메서드를 사용한다.
  • 일반 해쉬 맵의 get()의 경우, 탐색을 할 때마다 내부에서 hashcode(), equals() 등을 실행함으로써 추가적으로 연산을 하게 된다. 따라서 entrySet() 사용을 권장한다. (프로그래머스 문제 답변 참고)

2. 폰켓몬

• 문제 접근 : 각각 폰켓몬 종류 번호를 명단으로 저장한 뒤, 이들의 가짓 수를 파악한다. 총 개수의 절반과 폰켓몬 가짓 수를 비교하여 값을 반환한다. 총 개수의 절반이 가짓 수보다 많다는 것은 분명 겹치는 폰켓몬이 있다는 뜻이며 최대로 가져갈 수 있는 폰켓몬 가짓 수가 총 개수의 절반보다 적다는 뜻이다. 따라서 이 때는 가짓 수가 최대로 가져갈 수 있는 갯수이다.
  • 해쉬 맵을 사용할 경우, 숫자번호와 개수를 저장하는 <Integer, Integer>로 저장한다. 사실 가짓수를 파악하는 것이기 때문에 Value는 필요하지 않다.
  • 오히려, 중복을 제거해주는 해쉬 셋을 사용하면 객체만을 저장하는 자료구조로 적합하다.

• 해쉬 맵을 사용할 경우

import java.util.*;
class Solution {
    public int solution(int[] nums) {
        Map<Integer, Integer> hMap = new HashMap<>();
        for(int mon : nums) hMap.put(mon, hMap.getOrDefault(mon, 0) + 1);
        int keyNum = hMap.keySet().size();
        
        int len = nums.length/2;
        int answer = (keyNum >= len) ? len : keyNum;
        return answer; 
    }
}

• 해쉬 맵으로 폰켓몬을 저장한 뒤, keySet을 통해(Set이기 때문에 중복된 Key가 없어서 가짓수를 알 수 있음) 가짓수 keyNum을 구한다. 가짓수와 총 갯수의 절반 값을 비교하는 삼항 연산자를 통해 반환 값을 결정한다.
  • 따라서 해쉬 맵을 사용하여 내부의 Set을 사용하는 과정을 아예 해쉬 셋으로 저장함으로써 과정을 생략시킬 수 있다.

• 해쉬 셋을 사용할 경우

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

• 해쉬 셋은 내부에서 해쉬 맵을 생성하여 사용하기 때문에 해쉬 맵보다 속도가 느릴 수 있다. 하지만 위와 같은 경우엔 코드가 훨씬 간결해지고, 따로 값을 가져오는 연산을 수행하지 않기 때문에 해쉬 맵을 사용했을 때보다 속도는 더 빠르다.

3. 결론 : 이처럼 해쉬를 사용할 경우 데이터를 저장하고 조회하는 것이 빠르고 간단하다. (내부에서 해싱 알고리즘을 사용하기 때문에)