[프로그래머스 - 해시] Hash(해시)에 관하여, Hash에 관한 문제들

해시는 저번에 한 번 다룬 적이 있다. (https://oueya1479.tistory.com/2)
해시 테이블에 관한 내용이지만, key - value 값으로 value를 찾는다는 점에서 일맥상통한다.

자료를 저장하는 방법에는 stack, queue 등을 지금까지 알아보았고, 그 외에도 문제를 풀 때에 List, Set, Map에 대해 다룬적이 많았다. 각각 저장하고, 추출하는 방법에 사용자가 느끼기에는 별 다른 부분이 없다고 생각하겠지만, 점차 공부함에 따라 어떤 부분이 장점이 있고, 왜 그 부분에 대한 장점이 있을 수 밖에 없는지에 대한 이유를 알게 되는 것 같다.

그러면 Hash는 왜 쓰이고, 자료구조에서도 찾아볼 수 있는 HashSet, HashMap은 무슨 장점을 가져다 주는지 확인해보자.

Hash

ArrayList는 데이터를 추가하거나, 삭제할 때에 그 뒤에있는 모든 요소들이 앞당겨지거나 뒤로 밀려나는 현상이 발생하기 때문에 데이터가 자주 변경될 때에는 다른 자료구조보다 성능이 좋지 않을 수 있다.
다른 예시로는, LinkedList의 경우 데이터가 추가되거나 삭제될 때에 주변에 있는 노드만 수정해주면 되기 때문에 다른 노드들의 영향이 크지 않아 데이터 변경이 될 때에는 용이하지만, 검색의 경우에는 처음의 노드부터 마지막까지 돌기 때문에 느리다고 할 수 있다.

이러한 단점을 극복하고자 Hash가 나왔고, Hash는 검색의 측면에서 가장 효율적인 알고리즘으로 구성되어 있어 검색에 용이하다. Hash는 내부적인 인덱스를 이용하며, 데이터를 앞당기거나 뒤로 밀 필요가 없이 해당 값에 대한 고정된 길이로 이루어진 데이터와 매핑하여 내부 인덱스에 저장한다. 말로만 들으면 나도 이해하지 못한다. 사진을 살펴보자.

자바 [JAVA] - Hash Set (해시 셋) 구현하기(https://st-lab.tistory.com/240)

즉, 특정 데이터는 Hash function에 의해 그 데이터에 고정된 값으로 변환되고, 그 고정된 값은 내부 인덱스에 저장되어 있어 데이터의 변경에도 밀리는 현상이 없이 추가/삭제될 수 있는 것이다.

우리가 앞으로 문제를 풀어볼 것들은 이 Hash를 이용하여 구현된 HashSet과 HashMap에 대해서 살펴볼 것이다.
key-value의 형태를 통해 지속적으로 검색하면서 문제를 풀어나가야 하는 경우 hash를 사용하면 된다. value에 어떤 의미가 부여되어 있지 않아도 된다(HashMap에서 value로 설정할 것은 없어도 key만 활용해도 된다는 의미이다).

다음은 프로그래머스의 '완주하지 못한 선수'라는 문제이다. 자세한 규칙과 설명은 직접 사이트에서 찾아보기 바란다.
파라미터로 들어오는 participant는 참가자, completion은 완주자이며, 단 한명만 완주를 하지 못했을 때, 그 사람이 누구인지 찾는 문제이다. 동명이인이 있을 수 있기 때문에 그 점도 유의해야 한다.

즉, participant.length - 1 = completion.length 라는 의미가 되겠다.
프로그래머스에서 가져온 예시를 보여주겠다.
한 번 시도해보고 다음의 풀이를 보기 바란다.

예시

participant	completion	return
["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

 

import java.util.Map;
import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        /* String은 참가자의 이름이 들어갈 곳, Integer은 해당 이름이 얼마나 나왔는지 파악할 곳 */
        Map<String, Integer> hm = new HashMap<String, Integer>();
        
        /* 참가자의 수 만큼 이름을 Map에 삽입한다.
         * 이 때 getOrDefault는 get과 같이 해당 key에 관하여 value를 가져오라는 말이지만
         * key가 존재하지 않을 때에는 default 값으로 반환한다는 의미이다. */
        for(String name: participant){
            hm.put(name, hm.getOrDefault(name, 0) + 1);
        }
        
        /* 완주자의 수 만큼 해당 key의 value값에서 1씩 뺀다. */
        for(String name: completion) {
            hm.put(name, hm.getOrDefault(name, 0) - 1);
        }
        
        /* 참가자의 value가 1인 key는 결국 완주하지 못했다는 것을 의미한다. */
        for(String name: participant) {
            if(hm.get(name) == 1) {
                answer = name;
                break;
            }
        }
        
        return answer;
    }
}