HashTable Algorithm 사용

HashTable 사용

저번 포스팅에서 HashTable을 구현 해보았다. 다소 많이 부족한 소스이지만 이번 포스팅에서는 해당 HashTable을 사용하여 알고리즘 문제를 하나 풀어보려고 한다. 본 문제는 

https://programmers.co.kr/learn/courses/30/lessons/42576 해당 링크에서 풀어 볼 수 있다. 해당 문제는 해시로 풀어 낼 수 있어서 이전에 구현 했던 HashTable을 사용해 보았다.

해당 문제를 해시로 풀 수 있는 이유는 각 선수들의 이름을 키로 해쉬 테이블을 구성 한 뒤 찾으면서 찾은 선수들을 지워가면서 지워지지 않는 선수는 완주를 하지 못한 사람임이 보장되기 때문이다. 

여기서 솔루션 부분을 구현해야 했는데 솔루션 클래스의 내용은 아래와 같고, 나머지 HashTable 구현 내용은 이전 Hash&HashTable Algorithm 설명 및 구현 포스팅에서 구현한 것을 그대로 사용하였다. 

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashTable hashTable = new HashTable(100000);
        
        for(String com : completion) {
            hashTable.put(com, com);
        }
        
        for(String parti : participant) {
            if(!hashTable.remove(parti)) {
                answer = parti;
            }
        }
		
        return answer;
    }
}

최초에 해시 테이블 크기를 정하여서 객체를 생성한 뒤 성공한 사람들의 배열 기준으로 해시테이블을 생성한다.  그러고 참여자를 기준으로 해시테이블에서 참여자와 동일한 이름의 사람을 찾으면서 지워나가면서 지워지지 않은 사용자는 완주하지 못한 사람임으로 결과 값으로 리턴 되어진다. 

결과 확인

깔끔하게 성공하는 모습을 볼 수 있다. 속도 또한 상당히 빠른 것을 볼 수 있는데 해시 테이블의 장점이다. 물론 해당 문제는 다른 방법으로도 풀 수 있다. 다른 사람들 풀이를 보니까 정렬을 이용한 방법, 기존 자바에서 제공하는 HashTable을 사용한 경우 등 여러가지 있었지만 직접 만든 HashTable알고리즘을 테스트 해보고자 만든 HashTable을 사용하였다.