[알고리즘 / Kotlin] 프로그래머스 - 위장(해시)

위장

문제 설명

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

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

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

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

입출력 예제

내 풀이

일단 문제를 풀기 위해 다음 2가지를 생각하였습니다.

1. clothes에 있는 2차원 배열에서 의상의 종류에 따라 의상이 몇 개 있는지에 대한 정보를 어떻게 표현할 것인가? -> 해시를 만들어야 겠다. { key : 의상의 종류 , value : 의상의 갯수}
2. 스파이가 입을 수 있는 옷의 조합을 어떻게 계산할 것인가?

일단 1번을 해결하기 위해 foreach를 통해 순회하면서 의상의 종류를 key 값으로 해당 종류의 의상이 몇 개인지를 value로 하여 HashMap의 형태로 저장하였습니다.

 

HashMap의 Key의 존재 여부는 containsKey()를 사용하여 구현하였습니다.

 

그리고 2번에서는 일단 의상의 종류에 따라 입을 수도 있고 안 입을 수도 있기 때문에 (의상의 종류의 개수 + 1)

가 하나의 종류에 대한 경우의 수가 되므로 만약 의상의 종류가 A, B, C라고 하면 전체 가짓수는 (A의 개수 +1)* (B의 개수 +1) * (C의 개수 +1)가 됩니다. 하지만 주의해야 할 것은 제한 사항에 스파이는 최소 하루의 의상을 입으므로 아예 입지 않는 경우의 수 1가지를 빼줘야 합니다.

 

이때 이 경우의 수를 계산하기 위해서 fold를 사용했습니다. fold는 초기값을 설정하여 해당 리스트의 데이터들을 모두 모을 수 있는 함수입니다.

 

내 코드는 다음과 같습니다.

class Solution {
    fun solution(clothes: Array<Array<String>>): Int {

      val clothesMap : HashMap<String, Int> = HashMap()

      //{의상 종류 : 갯수}  해시맵 생성
      clothes.forEach {
        if(clothesMap.containsKey(it[1]))
            clothesMap[it[1]] = (clothesMap[it[1]] ?: 1) + 1;
        else
            clothesMap[it[1]] = 1
        }

       //경우의 수 계산
        var answer = clothesMap.values.fold(1){
        acc, i -> acc * (i+1)
        }

        return answer-1
    }
}

다른 사람들의 풀이

예제 1

class Solution {
    fun solution(clothes: Array<Array<String>>): Int {
        return clothes.groupBy { it[1] }.values.fold(1) { acc, v -> acc * (v.size + 1) }  - 1
    }
}

예제 2

class Solution {
    fun solution(clothes: Array<Array<String>>) = clothes
        .groupBy { it[1] }.values   // group by type of clothes, keep only names of clothes
        .map { it.size + 1 }        // number of things to wear in a group (including wearing nothing)
        .reduce(Int::times)         // combine
        .minus(1)                   // remove the case where the spy wears nothing
}

위의 예제 2개 모두 Kotlin의 장점인 간결함을 잘 활용한 것 같습니다.

배운 점

다른 분들의 풀이를 보고 Map 변수를 선언 안 하고 한 줄로 해결한 걸 보고 감탄했습니다. 나 스스로도 조금 더 Kotlin에 대해 공부를 열심히 해야겠다고 생각했습니다.

 

그리고 공통적으로 groupBy() 함수를 사용했는데 다음과 같은 기능을 하는 함수라고 합니다. (꼭 기억해두고 활용!!)

groupBy

특정 List의 원소에서 조건에 따라 두 값을 묶어서 Map의 <Key, Value> 타입으로 만듭니다.

• Key : group으로 묶어줄 조건
• Value : Key 조건에 만족하는 데이터들의 리스트

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

    val arr  = clothes.groupBy { it[1] } 

이런 식으로 하면 데이터의 2번째 요소를 기준으로 그룹화시켜줍니다. (아래 이미지 참고)

아직 내가 모르는 Kotlin Collection 관련 함수들이 많은 것 같아서 다음에 다시 한번 쭉 정리를 해야겠다고 생각했습니다. 프로그래머스에 해시 관련 Level 3 문제가 하나 있는데 이번 기회에 도전을 해봐야겠습니다.