TIL 27일차 (의상 - Kotlin)

코드카타

 

의상

 

문제

 

서로 다른 옷의 조합 수를 반환하는 문제이다.

 

 

입출력 예시

 

 

조합의 개수

1) 의상의 종류가 1가지인 경우 (의상 A: a개)

코니는 최소 하루에 한 개의 의상은 입는다고 언급이 되어있기에

한 가지 종류의 옷을 1번씩 입게되어 a개의 조합이 가능하다.

 

2) 의상의 종류가 2가지인 경우 (의상 A: a개, 의상 B: b개)

의상을 한 가지씩 입는 경우의 수: a + b,

의상 2개를 섞어 입는 경우의 수: ab 

총, a + b + ab 개의 조합이 가능하다.

 

3) 의상의 종류가 3가지인 경우 (의상 A: a개, 의상 B: b개, 의상 C: c개)

의상을 한 가지씩 입는 경우의 수: a + b + c

의상 2개를 섞어 입는 경우의 수: ab + ac + bc

의상 3개를 섞어 입는 경우의 수: abc

총, a + b + c + ab + ac + bc + abc 개의 조합이 가능하다.

 

 

공식 찾기

옷의 종류 1가지 : (a + 1) - 1 = a
옷의 종류 2가지 : (a + 1)(b + 1) - 1 = ab + a + b + 1 - 1
옷의 종류 3가지 : (a + 1)(b + 1)(c + 1) - 1 = abc + ab + ac + bc + a + b + c + 1 - 1

의상 종류 수만큼 (각 의상 종류의 개수 + 1)을 반복해서 곱해준 뒤 1을 빼면

주어진 의상에서 서로 다른 옷의 조합 수를 구할 수 있다.

 

 

조합론의 곱의 법칙

위 예제에서 사용한 개념은 조합론에서 곱의 법칙에 해당한다,

곱의 법칙이란 각 선택지를 독립적으로 고려하여 전체 조합의 수를 구하는 방식이다. 

각 선택이 독립적이며 중복되지 않기에 단순 곱셈으로 전체 경우의 수를 구할 수 있다.

 

 

풀이

class Solution {
    fun solution(clothes: Array<Array<String>>): Int {
    	// 의상의 종류와 개수를 매핑한다.
        val map = mutableMapOf<String, Int>()
        for(i in clothes){
            map[i[1]] = map.getOrDefault(i[1], 0) + 1 
        }
        
        // 공식을 활용해 서로 다른 옷의 조합 수를 구한다.
        var res = 1
        for(i in map.values){
            res *= i+1;
        }
   		
        // 마지막으로 1 빼주기
        return res - 1 
    }
}

맵을 이용하여 각 의상 종류의 개수를 구한 뒤,

입출력 예시를 통해 알아낸 공식을 활용하면 쉽게 답을 구할 수 있다.

 

 

회고

문제 설명이 아주 상세하게 되어있어, 풀이가 상대적으로 쉽게 느껴졌다.

 

본인은 짧고 가독성 있는 코드를 선호하는데 

이번 문제는 로직을 알기 쉽게 코드를 짠 것 같아 만족스럽다.

 

앞으로 문제 풀이에 접근할 때, 테스트 케이스를 분석하여

수학적 개념을 적용하는 방법도 고려해봐야겠다.