[프로그래머스/Kotlin] Lv2 의상 : 해시

분류

해시

문제 설명

코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.

예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다.

종류	이름
얼굴	동그란 안경, 검정 선글라스
사의	파란 셔츠
하의	청바지
겉옷	긴 코트

• 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
• 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
• 코니는 하루에 최소 한 개의 의상은 입습니다.

코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

문제 풀이 아이디어

[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]] 과같이 clothes 의 입력을 받기 때문에, 각 배열의 1번 index의 값을 key로 type들을 나눈다. 그리고 각 type에 yellow_hat,green_turban 을 넣는 linkedHashMap을 만들었다. 그리고 각 type을 하나 이상 선택에서 입을 수 있는 조합을 계산한다. 계산 방법은 아래와 같다.

상의 A,B 모자 A가 있다고 가정하자.

상의	모자
상의 A	x
상의 B	x
상의 A	모자 A
상의 B	모자 A
x	모자 A
x	x

이렇게 경우의 수가 나올 수 있다. 하지만 하나의 타입은 반드시 착장해야하므로 맨 마지막 경우는 해당되지 않는다.

위 표를 일반화 시키면 상의 A,상의 B, 상의 입지않음/ 모자 A, 모자 입지않음 이라는 종류가 존재하면 각 종류의 수인 (3x2)-1(전부 안 입는 경우 뺄셈)  의 값이 해당 종류로 조합할 수 있는 코디의 수다. 

따라서 clothes에서 나눈 type을 key로 하는 value의 수를 전부 곱하고 전부 안 입는 경우를 뺄셈해주면 답을 구할 수 있다. 

코드

import java.util.*


class Solution {
    fun solution(clothes: Array<Array<String>>): Int {
        var clothesCategory = 0
        var category = LinkedHashMap<String, LinkedList<String>>()
        clothes.forEach {
            if (!category.containsKey(it[1])) {
                category.set(it[1], LinkedList())
                clothesCategory ++
            }
        }

        for (i in clothes.indices) {
            category.forEach {
                if (it.key == clothes[i][1]) {
                    category[it.key]!!.add(clothes[i][0])
                }
            }
        }

        var answer = 1
        category.forEach{
            answer = answer * (it.value.size+1)
        }
        return answer-1
    }
}

나는 linkedHashMap을 사용했지만, 그냥 hashMap을 사용해도 될 거 같다. 또한 예시로 headgear와 같은 key의 value count만을 사용하기 때문에 굳이 key에 해당하면 value를 일일이 hashMap에 넣지 않고, 입력을 받을 때 count만을 ++ 해서 문제를 풀 수 있을 것 같다. 

forEach와 containsKey를 알고 있다면 쉽게 풀 수 있는 문제이다.