[프로그래머스/Lv2] 위장

문제

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

 

예를 들어 스파이가 가진 옷이 아래와 같고

오늘 스파이가 동그란 안경, 긴 코드, 파란색 티셔츠를 입었다면

다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 한다.

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

 

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 반환하는 함수를 만들어야 한다.

 

 

제한사항

1. clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있다.

2. 스파이가 가진 의상의 수는 1개 이상 30개 이하이다.

3. 같은 이름을 가진 의상은 존재하지 않는다.

4. clothes의 모든 원소는 문자열로 이루어져 있다.

5. 모든 문자열의 길이는 1이상 20이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있다.

6. 스파이는 하루에 최소 한 개의 의상은 입는다. 

 

 

코드

from math import factorial

def solution(clothes):
    def combination(n, r):
        return factorial(n) // (factorial(r) * factorial(n-r))

    cloth_dict = {}
    for cloth in clothes:
        try:
            cloth_dict[cloth[1]] += 1
        except:
            cloth_dict[cloth[1]] = 1

    answer = 1
    for value in cloth_dict.values():
        answer *= combination(value, 1) + combination(value, 0)
    
    return answer - 1

 

 

설명

이 문제도 문제 설명만 보면 이해가 잘 안된다.

프로그래머스에 이 문제를 직접 보러 가면 입출력 예시가 나오는데 그 예시를 보는 편이 이해가 더 잘된다.

 

이 문제는 조합으로 푼다.

종류라는 상자 안에 있는 이름이라는 공들을 하나 꺼내는 경우의 수 + 하나도 꺼내지 않는 경우의 수를

종류별로 계산하여 곱하면 우리가 원하는 의상 조합의 경우의 수가 나오게 된다.

 

이 때 문제에서 스파이는 최소 한 개의 의상은 입는다고 했으니

모든 공을 꺼내지 않는 경우를 마지막에 빼준다.

 

def combination(n, r):
	return factorial(n) // (factorial(r) * factorial(n-r))

조합 공식을 그대로 함수로 만든 것이다.

 

cloth_dict = {}

옷 종류 별로 몇 개의 의상이 있는 지를 기록할 딕셔너리이다.

 

for cloth in clothes:
	try:
		cloth_dict[cloth[1]] += 1
	except:
		cloth_dict[cloth[1]] = 1

try, except 문을 활용해서 cloth_dict에 종류별로 의상의 개수를 기록한다.

 

answer = 1
for value in cloth_dict.values():
	answer *= combination(value, 1) + combination(value, 0)

값을 반복해서 곱해줄 것이기 때문에 answer 변수는 1로 초기화해둔다.

 

cloth_dict의 값들만을 반복해서 꺼내며 아래 코드를 실행한다.

공을 상자에서 하나만 꺼내는 경우의 수(\(value \choose 1\ \))에 하나도 꺼내지 않는 경우의 수(\(value \choose \ 0 \))를 더한 값을 answer에 곱해준다.

 

return answer - 1

모두 꺼내지 않는 경우를 제외하고(1을 빼줌) answer를 반환한다.