문제
스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.
예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.
스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항
clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
같은 이름을 가진 의상은 존재하지 않습니다.
clothes의 모든 원소는 문자열로 이루어져 있습니다.
모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
스파이는 하루에 최소 한 개의 의상은 입습니다.
접근
해시 테이블을 통해서 풀어야 한다는 것은 문제에서부터 보였다. 그래서 주어진 의상 정보와 종류대로 맵을 만들었지만 의상의 갯수를 계산하는 것이 문제였다. 가장 먼저 생각난 풀이 방법은
만약
- 머리 : 2종류
- 상의 : 3종류
- 하의 : 2종류
이렇게 해시 테이블이 만들어진다면
1개 의상 종류만 착용하는 경우
머리만 착용하는 경우 2가지
상의만 착용하는 경우 3가지
하의만 착용하는 경우 2가지
=> 총 7가지
2개 의상 종류를 착용하는 경우
머리 + 상의의 경우 2 3가지
머리 + 하의의 경우 2 2가지
상의 + 하의의 경우 3 * 2가지
=> 총 16가지
3개 의상 종류를 착용하는 경우
머리 + 상의 + 하의를 전부 착용하는 경우 2 3 2가지
=> 총 12가지
이렇게 총 35가지의 경우의 수가 나온다.
하지만 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다. 라는 제한 조건이 있다고 해도 worst case의 경우 반복문을 30번 돌아야 하고 몇 종류의 의상이 나올지 모르므로 이 반복문도 재귀로 돌려주어야 했다.
한참을 생각하다가 구글링을 해서 찾아본 결과 이러한 문제에 대한 간단한 수학 공식이 있었다. 바로 각 의상의 개수에 1을 더한 후 전부 곱한다음 1을 빼주는 것이었다. 이 공식은 의상의 개수에 따라 의상을 입는 경우에 수에 안입는 경우의 수 1을 더해주고 가장 마지막에 모든 의상을 안입는 경우의 수 1을 빼는 것이 알고리즘 해결을 방법이었다. 중, 고등학생때 어디선가 봤던 문제였는데 여기서 이렇게 만나니 참 안반가웠다. 통과한 코드는 아래와 같다. 다시보니 buildMap 메소드에서 의상 이름을 ArrayList에 추가하는 것이 아니라 1씩 더해주면서 size를 직접 주어도 됐을 것 같다.
import java.util.*;
class Solution {
public int solution(String[][] clothes) {
Map<String, List<String>> map = buildMap(clothes);
System.out.println(map);
Iterator it = map.keySet().iterator();
int sum = 1;
while(it.hasNext()){
String key = String.valueOf(it.next());
System.out.println(key);
int clothes_num = map.get(key).size() + 1;
sum= sum * clothes_num;
}
return sum-1;
}
private Map<String, List<String>> buildMap(String[][] clothes){
Map<String, List<String>> map = new HashMap<>();
for(String[] c : clothes) {
map.put(c[1], new ArrayList<>());
}
for(String[] c : clothes){
List<String> curr = map.get(c[1]);
curr.add(c[0]);
}
return map;
}
}