프로그래머스 의상-level2

옷의 종류 n개중 1..개까지 고르는 경우의 수를 구해야한다

즉, nC1 + nC1+1 + .. + nCn 까지의 경우를 모두 구하고

각조합일때 의상의 경우의수를 곱해서 누적해야한다

 

코드

fun solution(clothes: Array<Array<String>>): Int {
    var answer = 0

    val list = clothes.toMutableList()

    val hashMap = HashMap<String,Int>()

    var group = list.groupBy { it[1] }

    group.forEach {
        hashMap[it.key] = it.value.size
    }

    //println(hashMap)

    //println(hashMap.count { it.key == "headgear" })

    //옷종류 리스트를 만든다
    val clothesCategoryList:List<String> = list.map { it[1] }.distinct()

    //한개만 고를떄
    answer += clothes.size

    if (clothesCategoryList.size == 1){
        return answer
    }

    val countList = mutableListOf<Int>()
    val categoryList = mutableListOf<List<String>>()


    for (i in 2 .. clothesCategoryList.size-1){
        //i는 n개의 옷종류중 i개를 선택할경우
        //for문은 2.. n-1개의 종류의 옷을 선택해서 옷을 고르는 경우를 누적함
        // n개의 종류중 i개를 선택했을떄 선택한 옷종류 i개를 담을 리스트
        combination(categoryList, clothesCategoryList, Array<Boolean>(clothesCategoryList.size) { false }, 0,  i)

        categoryList.forEach { category->

            category.forEach { k->
                val num = hashMap[k]
                if (num != null) {
                    countList.add(num)
                }
            }
            var sum = 1
            countList.forEach { c->
                sum*=c
            }

            countList.clear()

            //println(countList)
            //println(sum)

            answer+= sum
        }
        categoryList.clear()


    }




    //종류별로 한개씩만 고를때
    val clothesGroup = list.groupBy { it[1] }
    var temp = 1
    clothesGroup.forEach {
        temp *= it.value.size
    }
    answer += temp


    return answer
}

fun <T> combination(answer: MutableList<List<T>>, el: List<T>, ck: Array<Boolean>, start: Int, target: Int) {
    if(target == 0) {
        answer.addAll( listOf(el.filterIndexed { index, t -> ck[index] }) )
    } else {
        for(i in start until el.size) {
            ck[i] = true
            combination(answer, el, ck, i + 1, target - 1)
            ck[i] = false
        }
    }
}

 

결론은 이코드는 정답이 아니다 1번을 제외한 모든 케이스에서 통과하지만 1번에서 시간초과가 뜬다

 

이유는 옷의 종류가 최대 30인데 옷의 종류가 30에 가까워지면이라면 연산의 10억회를 넘어간다

ide에서 해봤더니 결과가 나오기까지 1시간(?)이 걸렸다..

 

그리고 저 모든 조합을 구하는 콤비네이션코드를 구현하려고 굉장히 애를 썼지만 결국 구글링으로 찾아내서 사용했다

근데 코틀린에는 내장함수로 존재한단다 그냥 파이썬으로 가야하나 고민이다,,

 

-문제-

https://school.programmers.co.kr/learn/courses/30/lessons/42578?language=kotlin