[Baekjoon] 9375번: 패션왕 신해빈

https://www.acmicpc.net/problem/9375

9375번: 패션왕 신해빈

문제 설명

기본적인 조합 문제이다. 예제 1로 예를 들면 headgear라는 의상 종류에 hat, turban이라는 두 의상이 있고, eyewear에 suglasses라는 하나의 의상이 있다. 이 경우 {hat}, {turban}, {sunglasses},{hat, sunglasses}, {turban, sunglasses}로 총 5일동안 알몸이 아닐 수 있다.

 

주의할 점은 만약 vans-shoes 라는 의상이 있다고 하면 {hat, sunglasses, vans}, {turban, sunglasses, vans}는 안 된다는 점이다. {sunglasses, vans}라는 조합이 반복되었기 때문이다.

 

또 주의할 점은 옷을 아예 안 입는 경우도 있다는 거다. headgear가 2개이므로 headgear에서 경우의 수가 2가지라고 생각할 수 있지만 headgear를 안 쓰는 {sunglasses}의 경우의 수도 있다.

 

따라서 headgear에서는 3C1을 구하면 되고, eyewear에서는 2C1을 구하면 된다. 그리고 이 둘을 곱하면 모든 조합의 경우의 수가 나온다. 그런데 이 경우 모든 옷을 안 입은, 즉 공집합이 포함되어 있기 때문에 결과값에서 1을 빼줘야 한다.

풀이 방법

HashMap을 이용해서 옷의 개수를 저장한다.

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            Map<String, Set<String>> map = new HashMap<>();
            int numOfClothes = Integer.parseInt(br.readLine());

            while (numOfClothes-- > 0) {
                String[] split = br.readLine().split(" ");
                String name = split[0];
                String type = split[1];
                if (map.containsKey(type)) {
                    map.get(type).add(name);
                } else {
                    Set<String> set = new HashSet<>();
                    set.add(name);
                    map.put(type, set);
                }
            }

            int ans = 1;

            for (Set<String> value : map.values()) {
                // 옷이 없는 경우도 있으므로 +1해서 곱해준다.
                ans *= value.size() + 1;
            }

            // 알몸인 날은 뺀다.
            sb.append(ans - 1).append("\n");
        }
        System.out.print(sb);
    }
}