프로그래머스 - 위장 해시

해시 문제 풀이

 

 

코딩테스트 연습 - 위장

위 문제에서 해결을 해야 할 부분은 두가지이다.

1. 해시맵을 이용하기

2. 조합을 구하기

 

 

직접 만든 가벼운 해시 함수 

fun customHash(keyString: String): Int {
    var key: Int = 0
    for (i in keyString) {
        key += i.code
    }
    return key
}

하지만 너무 가벼워서 그런지 테스트하니 바로 해시 충돌이 났다. 

 

- 들어오는 코드

val question: Array<Array<String>> = arrayOf(
        arrayOf("yellowhat", "headgear"),
        arrayOf("bluesungla", "eyewear"),
        arrayOf("green_turban", "headgear")
    )

 

- 풀이 코드

fun solution(clothes: Array<Array<String>>): Int {
    var answer = 1
    
    //해시 를 사용한 값 분리
    val clothesMap: HashMap<String, Int> = hashMapOf()
    clothes.forEach { element ->
        if(clothesMap.containsKey(element[1])) {
            val updateValue = clothesMap[element[1]]?.plus(1) ?: 0
            clothesMap[element[1]] = updateValue
        } else {
            clothesMap[element[1]] = 1
        }
    }

    //조합을 이용
    clothesMap.forEach {
        answer *= (it.value + 1)
    }

    return answer - 1
}

그래서 위와 같이 HashMap을 사용하였으며 <String, Int> 로 선언하여 String에 key가 중첩될 경우에 value 를 +1 씩 늘려주었다.

즉, key 는 옷의 종류이고 옷의 종류가 늘어날때마다 value가 증가한것.

 

두번째로 조합을 이용해 주어야 하는데,

3가지 옷종류가 있다고 한다면,

 

000

001

010

100

011

101

110

111

 

과 같은 경우의 수가 생겨난다. 하지만 여기에서 000 인 아무것도 입지 않는 경우를 제외해야 하므로 총 갯수에서 -1개를 해주면 답을 구할 수 있다.