Kotlin algorithm - Hash (1)

프로그래머스

https://github.com/jhk-im/jhk-algorithm/tree/main/kotlin/01_hash/test1

GitHub - jhk-im/jhk-algorithm

 

* ArrayList는 인덱스를 이용하여 검색이 한번에 이루어지기 때문에 검색 속도를 보장하는 반면 데이터의 추가/삭제시에는 많은 데이터가 다같이 이동해야 하기 때문에 많은 시간이 소요된다. 

array_img

 

* 추가/삭제시 마주하는 한계를 극복하기 위해 제시된 방법이 Hash이다. 기존 데이터를 밀어내거나 당기는 작업이 필요없도록 특별한 알고리즘을 이용하여 데이터와 관련된 고유한 숫자를 만들고 이를 인덱스로 사용한다. Key-Value 방식으로 저장하며 여기서 Key값을 계산하는 것이 Hash Method이다. 그렇게 반환 된 데이터 고유 값을 Hash Code라고 한다. 그리고 이러한 방식으로 Table에 저장하고 검색하는 방법을 Hashing이라 한다. 

hash_img

 

* String 클래스에서 Hash Method인 hashCode()를 오버라이딩 하여 문자열의 내용으로 고유값을 생성한다. 서로 다른 인스턴스이지만 같은 내용의 문자열을 가졌기 때문에 hashCode()호출 시 같은 값을 얻는다. HashMap도 같은 방법으로 객체를 구별하며 이미 존재하는 키와 동일한 값을 저장하는 경우 기존의 값에 덮어쓴다.  

val s1 = "string"
val s2 = "string"
print(s1.hashcode()) // -891985903
print(s2.hashcode()) // -891985903
print(s1==s2) // true

val hashMap = HashMap<String, Int>()
hashMap["s1"] = 1
hashMap["s2"] = 3
hashMap["s2"] = 2
print(hashMap)

hash_img_2

 

* 프로그래머스 코딩테스트의 문제와 제한사항은 다음과 같다. 

전체 선수 배열과 완주 선수 배열이 주어질 때 완주하지못한 참가자를 찾아라. (완주하지 못한 선수는 1명)

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하
• completion의 길이는 participant의 길이보다 1 작음
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있음
• 참가자 중에는 동명이인이 있을 수 있음

* ArrayList를 사용할 때 문제점은 무엇인가? 

index는 단순히 순서를 나타내는 고유값이다. 그렇기 때문에 player A의 완주유무를 검사한다고 했을 때 전체선수 배열의 player A의 index와 완주선수 배열의 player A의 index가 동일할 것이라고 보장할 수 없으므로 player A의 완주 유무를 판단하기 위해서는 완주선수 배열에서 매치될 때 까지 전부 검사해야한다. 각각의 index의 검사 완료 시점또한 동일하지 않다. 중복된 player를 검사하는 것 까지 추가되면 더욱 복잡해진다. (ArrayList로 해결한 답안도 있다.)

arrayList match

 

 

* HashMap을 사용할 때 어떠한 이점이 있는가? 

전체선수 배열에서 선수의 이름을 Key값으로 하여 HashMap으로 정리 된다면 완주선수 배열의 선수명으로 HashMap Key값을 이용해서  빠르게 매치시킬 수 있다.

hash map match

전체선수 배열을 HashMap에 저장할 때 HashMap의 Key를 생성하는 hashCode()는 중복을 허용하지 않기 때문에 중복된 선수명 key값은 덮어쓰게 되는 문제가 있는데 다음과 같은 방식으로 중복 검사를 진행하여 해결한다. 

val map = HashMap<String, Int>()

// 1. 전체 선수배열에서 선수의 이름을 Key값으로 하여 HashMap에 저장한다. 
for (player : String in participant) {

    // 2. 이미 저장했던 선수인지를 let {} 을 통해 판단한다. 
    //    let {}은 자바의 if(value != null)을 대체하여 유용하게 사용된다. 
    map[player]?.let {
        // 3. 이미 저장했던 선수인 경우 기존 value에 + 1을 더한다. 
        map[player] = it + 1
    }

    // 4. 중복되지 않은 선수는 value를 1로 지정한다. 
    if (map[player] == null) {
        map[player] = 1
    }
}

 위 코드는 HashMap의 getOrDefault(Object, defaultValue)를 사용하면 간략하게 중복검사를 진행할 수 있다. getOrDefault()는 입력한 key값이 존재하는 경우 해당 key의 value를 반환하고 없을 경우 default값을 반환한다.  

for (player : String in participant) {
    map[player] = map.getOrDefault(player, 0) + 1
}

중복검사

아래와 같이 완주선수 배열의 선수명과 전체선수 HashMap의 Key를 매치시키고 value값에 1을 빼도록 한다. 완주한 선수는 0이되고 완주하지 못한 선수는 1이 될 것이다. 중복된 선수중 한명만 완주 했다면 마찬가지로 해당 선수의 vlaue는 1이 된다. 모두 완주했다면 value는 0이 된다.

for (player : String in completion) {
    map[player]?.apply {
        map[player] = this - 1
    }
}

완주선수 배열과 매치가 끝난 HashMap은 아래와 같이 Key값을 검사하고 value가 1인 선수를 찾으면 문제가 해결된다. 

for (key : String in map.keys) {
    if (map[key] != 0) {
        // map[key] -> 완주하지 못한 선수!
    }
}