1. 문제 분석
-
의상 이름과 종류가 공백으로 구분되어 주어집니다. 이 때, 서로 다른 옷의 조합을 구하는 문제입니다.
-
같은 종류의 의상은 하나만 입는것이 가능합니다.
-
동일한 이름의 의상은 없습니다.
-
알몸이면 안됩니다.
2. 접근방법 - 개념
위 문제는 조합에 대한 문제입니다.
예제를 토대로 예시를 들어보면,
이름 : hat, 종류 : headgear 입니다.
이러한 방식대로 정리해보면,
[heagear] - hat, turban
[eyewear] - sunglasses
이렇게 정리가 됩니다. 이를 조합으로 생각해보면, 각 옷의 종류 당 하나씩만 선택하여 하나의 의상이 나오게 됩니다.
hat, turban, sunglasses, hat-suglasses, turban-sunglasses
위처럼 5개의 경우의 수가 해당됩니다.
- hat-turban 과 hat-turban-sunglasses는 같은 종류를 2개 이상 선택했기 때문에 해당하지 않습니다.
이와 같은 방식으로 계산을 해보면, 저희가 예전에 기억 저편에 넣어두었던 순열과 조합이 생각 나실 겁니다.
💡 조합이란?
조합은 Combination으로 여러 선택 사항 중 순서에 상관없이(순서가 없으면, 같은것들을 빼고 샌 수) 필요한 만큼 뽑아내는 경우의 수를 구하는 개념입니다.
따라서, 하나의 종류 안에 1개 이상의 의상이 있는경우, 해당 의상은 갯수 중에서 하나를 선택해야하기 때문에 nCr의 공식이 성립하는 것입니다.
이를 문제에 적용해보면 다음과 같습니다.
[ face ] - mask, sunglasses, makeup
이렇게 나와있는 예제에서 하나의 종류에 3개의 값이 들어가 있는것을 확인할 수 있습니다. 이는 즉, 3C1을 의미합니다.
이는 3P1과도 동일한데 이는 순서를 보장하든 보장하지 않든 어차피 1개의 값만 뽑아내기 때문입니다.
따라서 경우의 수는 mask, sunglasses, makeup 총 3가지입니다.
3. 접근 방법 - 적용
문제에 개념을 적용해보면, 각 종류마다 갯수를 구하여 이를 1개씩 뽑는 경우의 수를 구해주면 됩니다.
필자는 Map을 사용하여 key - 종류, value - 의상갯수 로 지정하여 종류마다 전체 갯수를 확인 후, 각각의 경우의 수를 구하도록 구현하였습니다.
이 후에 해당 경우의 수들 간에 조합을 위해 각 경우의 수를 곱해주면, 전체 경우의 수가 출력됩니다.
⚠️ 주의
각 의상 종류들은 무조건 1개 이상 입어야 한다는 조건은 없습니다. 따라서 어떤 종류의 의상은 아예 입지 않는것이 가능합니다.(경우의 수 + 1씩)
또한, 문제에서 알몸일 때를 배제하라는 언급이 있었습니다. 이는 전체의 경우의 수에서 모든 의상을 입지 않은 1가지의 경우의 수만 빼주면 됩니다.
4. 구현
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
Map<String, Integer> map = new HashMap<>();
int t = Integer.parseInt(br.readLine());
StringTokenizer st;
while (t-- > 0) {
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
st.nextToken(); // 이름 사용 X
String kind = st.nextToken();
map.put(kind, map.getOrDefault(kind, 0) + 1);
}
int totalCount = 1;
for (int value : map.values()) {
totalCount *= (value + 1); // 착용하지 않는 경우의 수 +1
}
sb.append(totalCount - 1).append("\n"); // 알몸인 경우의 수 배제
map.clear();
}
br.close();
System.out.println(sb);
}
}