Hash 알고리즘 이해하기

💡 목적 : 알고리즘 풀이 중 for문으로 배열에 있는 모든 값을 하나하나 불러오니 시간이 너무 많이 걸리고 코드도 너무 길어져 복잡성 증가. 따라서 Hash함수를 사용하면 보다 간단하게 로직을 짤수있음

문제 - 프로그래머스 입문문제 <최빈값 구하기>

class Solution {
    public int solution(int[] array) {
        int answer = 0;
        int[] cnt = new int[1000];
        int max=0;
        int count=0;
        for(int i=0;i<array.length;i++){
            for(int j=0;j<1000;j++){
                if(array[i]==j) cnt[j]++;
            }
        }
        
        for(int i=0;i<cnt.length;i++){
            if(cnt[i]>max) {
                max = cnt[i];
                answer = i;
            }
        }
        for(int i=0;i<cnt.length;i++){
            if(max==cnt[i]) count++;
        }
        if(count>1) answer=-1;
        return answer;
    }
}

처음 내 코드인데 너무 복잡하고 for문이 많아서 시간이 많이걸림..

Hash란? key : value 로 받는 하나의 자료구조

• key : 검색어 / value : 검색해서 나온 값 으로 생각하면 편함
• Hash 함수의 특징 : 모든 데이터 타입으로 접근이 가능하다

예제

프로그래머스 완주하지 못한 선수 : N명의 마라토너중 N-1명만 완주했다고 할때 마지막 완주하지 못한 선수 찾기
A, B, C가 마라톤을 뛴다고 할때 A와 C가 완주했을때 B를 찾아야하는 상황

finished[A] = false, finished[B] = false, finished[C] = false 상태에서 배열을 다 돌면서 A와 C를 찾은 후 True를 집어넣는 방식은 나중에 사람이 100,000명이 넘어가면 너무 시간이 오래걸림

HashMap.put("A",true); 을 작성하면 HashMap["A"] = true;와 같은 동작을 함

HashMap.get("A"); 를 하면 bool fin = hashmap["A"];와 같은 동작을 함

하지만 HashMap.get("A") 라고 했을때 A에 아무런 값이 없다면 error가 발생한다.
따라서 등장한 getOrDefault 함수

getOrDefault함수란?

: HashMap.get("A")를 했을때 A에 값이 있으면 반환해주고 없다면 false를 반환

이 함수를 활용해서 코드 리펙토링 해보면

import java.util.*;

class Solution {
    public int solution(int[] array) {
        int maxcount = 0;
        int answer = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for(int number : array){
            int count = map.getOrDefault(number,0) + 1;
            if(count>maxcount){
                maxcount = count;
                answer = number;
            }
            else if(count == maxcount){
                answer = -1;
            }
            map.put(number,count);
        }
        
        return answer;
    }
}

시간을 비교해보면 속도면에서 80% 정도 절감됐음을 알수있다

테스트 1 〉	통과 (0.26ms, 77.6MB)
테스트 2 〉	통과 (1.48ms, 84.8MB)
테스트 3 〉	통과 (1.85ms, 79.5MB)
테스트 4 〉	통과 (0.60ms, 86.2MB)
테스트 5 〉	통과 (0.48ms, 76.5MB)
테스트 6 〉	통과 (0.09ms, 73.1MB)
테스트 7 〉	통과 (0.11ms, 72.3MB)
테스트 8 〉	통과 (1.58ms, 81.4MB)
테스트 9 〉	통과 (0.09ms, 85.2MB)
테스트 10 〉	통과 (0.07ms, 74.7MB)
테스트 11 〉	통과 (0.19ms, 74.4MB)
테스트 12 〉	통과 (1.12ms, 80.2MB)
테스트 13 〉	통과 (0.74ms, 80.6MB)
테스트 14 〉	통과 (0.96ms, 90.4MB)
테스트 15 〉	통과 (1.19ms, 86.7MB)
테스트 16 〉	통과 (0.62ms, 88.8MB)

테스트 1 〉	통과 (0.07ms, 72.8MB)
테스트 2 〉	통과 (0.23ms, 77MB)
테스트 3 〉	통과 (0.37ms, 73.3MB)
테스트 4 〉	통과 (0.06ms, 76.8MB)
테스트 5 〉	통과 (0.07ms, 83.8MB)
테스트 6 〉	통과 (0.05ms, 80.3MB)
테스트 7 〉	통과 (0.07ms, 87.7MB)
테스트 8 〉	통과 (0.12ms, 82.3MB)
테스트 9 〉	통과 (0.04ms, 86.1MB)
테스트 10 〉	통과 (0.03ms, 83.2MB)
테스트 11 〉	통과 (0.05ms, 86.2MB)
테스트 12 〉	통과 (0.17ms, 72.6MB)
테스트 13 〉	통과 (0.24ms, 70.3MB)
테스트 14 〉	통과 (0.22ms, 80.5MB)
테스트 15 〉	통과 (0.29ms, 76.2MB)
테스트 16 〉	통과 (0.11ms, 77.1MB)