위장

문제 설명

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

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

 

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

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

제한사항

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

입출력 예

clothes	return
[[yellow_hat, headgear], [blue_sunglasses, eyewear], [green_turban, headgear]]	5
[[crow_mask, face], [blue_sunglasses, face], [smoky_makeup, face]]	3

내가 푼 방법

문제를 보고 딱 든 생각은 일단 "저 입력을들 맵에 저장해놓으면 쓸만 하겠다" 였다. 맵은 키와 밸류로 데이터를 저장하니까 이 문제와 찰떡 궁합인 셈이다. 

 

c++에서 사용할 수 있는 map은 map과 unordered_map 두가지가 있는데 map은 레드블랙 트리를, unordered_map은 해쉬테이블을 사용한다. 이렇게 데이터가 적은 문제는 어느것을 사용해도 문제가 없어 보여서 해쉬테이블을 사용하는 unordered_map을 사용했지만 추후에 이 두개의 차이점에 대해 자세히 알아볼 필요가 있을듯 하다. 

 

입력으로 들어오는 두개의 문자열 쌍을 그대로 저장할려고 했지만 매우 어리석은 생각임을 깨달았다. 나는 옷을 입는 모든 경우의 수만 생각하면 될 뿐이었다. 굳이 옷이 어떤 이름을 가지고 있는지 알 필요가 없고 같은 이름의 의상이 없으므로 옷의 종류에 따른 옷의 갯수만 알고있으면 된다. 그래서 저번에 포스팅 했던 글([프로그래머스] - 완주하지 못한 선수)에서와 비슷하게 <string, int> 쌍으로 저장하고 같은 key가 들어오면 value를 1증가시키면 된다. 

 

그럼 이제 경우의 수를 구하는 방법에 대해 알아보자.

다음과 같이 상의2개 하의 2개가 있다고 할 때

1개씩 선택하는 경우의 수 - A,B,C,D 총 4개 (4C1)

2개씩 선택하는 경우의 수 - AC,AD,BC,BD 총 4개 (2C2 X 2C2)

이렇게 생각하니 옷의 종류가 많아질수록, 옷의 갯수가 많아질수록 뭔가 더 헷갈렸다.

옷의 종류가 3개만 돼도 1,2,3개씩 선택하는 경우에 따라 식이 복잡하게 바뀐다.

 

그런데 다음과 같이 해당 옷 종류를 선택하지 않는 경우의 수를 추가하면(X는 선택하지 않는것을 의미)

상의 경우의수 X 하의 경우의수 = AC,AD,AX,BC,BD,BX,XC,XD,XX

최소 한개 이상의 의상을 입어야 하므로 XX를 제외하면 모든 경우의 수가 다 나오게 된다.

 

따라서 옷의 종류만큼 for문을 돌면서 옷의 갯수+1 만큼 곱해주고 마지막에 -1만 해주면 된다.

소스코드