Kotlin algorithm - Hash (2)

프로그래머스

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

GitHub - jhk-im/jhk-algorithm

 

* 프로그래머스 2번째 코딩테스트의 문제와 제한사항

 

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 한다. 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성하라. 

• phone_book의 길이는 1 이상 1,000,000 이하
• 각 전화번호의 길이는 1 이상 20 이하
• 중복된 번호 없음 

* 프로그래머스에 작성된 답안을 보면 Hash를 사용하지 않고 통과한 답안도 있다. 중복된 번호가 없다는 점에서 배열을 전부 탐색하지 않고 중간에 break으로 빠져나갈 수 있기도 하고 startWith() 메소드를 사용해서 비교적 쉽게 접두어 포함여부를 확인할 수 있기 때문인 것 같다. 그렇긴 하지만 Hash카테고리 안에 있는 테스트이므로 위 문제가 Hashing의 장점을 활용해 어떻게 해결될 수 있는지를 아는 것 도 중요한 것 같다. 

 

1. Hash를 활용하기 위해 우선 입력되는 배열을 Hash에 전부 담는데 이 때 Key , Value에 모두 전화번호를 입력한다.  이번 문제에서 Value는 사용되지 않는다. 

val phoneBook = arrayOf("119", "97674223", "1195524421")

val hashMap = HashMap<String, String?>()

for (phone in phoneBook) {
    hashMap[phone] = phone
}

---

<"119", "119">
<"91674223", "91674223">
<"1195524421", "1195524421">

2. HashMap은 keys (java의 keySet()) 를 통해서 키 리스트를 배열처럼 활용할 수 있다. 해쉬맵에 담긴 전화번호를 다시한번 검색한다. 

for (key in hashMap.keys) {
    
}

3. Hash의 장점은 배열을 전부 검색하지 않더라도 Key를 입력하면 다이렉트로 입력된 Key값의 테이블에 접근 가능하다는 것이다. 

*HashMap의 containsKey() 메소드에 값을 입력하면 해당 값이 현재 HashMap에 Key로 존재하는지를 확인할 수있다.  Object가져올 필요 없으니 아주 적당한 메소드라고 볼 수 있다. 

hashMap["119"] // 119
hashMap.containsKey("119") // true
hashMap.containsKey("112") // false

 

4. 바로 접근 가능하다는것도 알겠고 containsKey()를 활용한다는 것도 알겠는데 가장 중요한 것은 접두어가 존재하는 지를 파악해야 한다는 것이다. 어떻게 하면 될까?

 

* key를 한글자씩 추가하면서 containsKey()에 입력하면 된다. "119"를 하나씩 추가한다고 했을때 "119"가 입력되면 이는 접두어가 아닌 자기 자신을 찾게되는 것이므로 "1" 과 "11"만 확인한다.  결과적으로 "119"의 접두어가 "1", "11"이 될수 있으므로 해당 값이 HashMap에 Key로 존재하면 접두어가 존재하게 되므로 false를 반환한다. 

<"119", "119">
1 
11

<"91674223", "91674223">
9
97
976
9767
97674
976742
9767422

<"1195524421", "1195524421">
1
11
119
false

5. 추출된 key를 마지막 한글자만 빼고 하나씩 추가하면서 입력하는 방법은 다음과 같다. 자바가 조금 더 직관적이라 같이 비교해서 확인해보자.

// java
for (String key : hashMap.keySet()) {
	// key.length() 보다 작을때까지 반복한다. 즉 마지막 글자 이전까지 반복한다. 
    for (int i = 0; i < key.length(); i++) {
        // Key가 첫 글자부터 더해지는 것은 substring() 메소드를 활용하면 된다.  
        // "(0,0) = "1"  -> (0,1) = "11" -> (0,2) = "119"
        if (hashMap.containsKey(key.substring(0,i))) return false;
    }
}

// kotlin
for (key in hashMap.keys) {
    for (i in key.indices) {
        if (hashMap.containsKey(key.substring(0, i))) return false
    }
}

 

* solution()

class HashCodingTest2 {

    fun solution(phoneBook: Array<String>): Boolean {
        val hashMap = HashMap<String, String?>()
        for (phone in phoneBook) {
            hashMap[phone] = phone
        }
        for (key in hashMap.keys) {
            for (i in key.indices) {
                println(key.substring(0, i))
                if (hashMap.containsKey(key.substring(0, i))) return false
            }
        }
        return true
    }
}

 

 * test

import hash.test2.HashCodingTest2

val hash2 by lazy { HashCodingTest2() }

val phoneBook1 = arrayOf("119", "97674223", "1195524421")
val phoneBook2 = arrayOf("123", "456", "789")
val phoneBook3 = arrayOf("12","123","1235","567","88")

fun main(args: Array<String>) {
    println(hash2.solution(phoneBook1))
    println(hash2.solution(phoneBook2))
    println(hash2.solution(phoneBook3))
}

 

결과 

1
11

9
97
976
9767
97674
976742
9767422

1
11
119
false

1
12

4
45

7
78
true

8

1

1
12
false