[Java] Boj 9375: 패션왕 신해빈

문제

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

 

풀이

 옷과 옷의 종류를 입력받고 같은 종류의 옷은 하나만 입을 수 있을 때, 입을 수 있는 옷의 조합 종류를 출력하는 문제이다. 문제를 보고 든 생각은 입력받은 옷들이 종류별로 몇 가지 있는지만 알면 바로 풀 수 있는 문제로 보였다. 옷이 종류별로 몇 가지 있는지 판정은 해시 맵을 이용하면 된다. 똑같은 옷이 입력으로 들어오지 않으니 단순히 한 종류의 옷이 몇 개 있는지만 알면 된다. 

 

 한 종류의 옷이 몇 개 있는지는 해시 맵을 이용해 구현 가능하니, 이제는 의상 조합 수를 따져보자. 상의 3개, 하의 4개, 모자 3개가 있을 때 조합 가능한 옷의 경우의 수는 (3 + 1) * (4 + 1) * (3 + 1) = 80가지가 될 것이다. 여기서 1을 옷의 종류마다 더해주는데, 이것은 해당 종류의 옷을 입지 않는 경우도 고려하기 때문이다. 추가로, 문제에서 아무것도 입지 않는 경우도 없다고 하였으니 이 경우의 답은 80 - 1 = 79가 될 것이다. 고등학교의 확률과 통계 공부할 때 이런 문제를 많이 봤던 것 같은데 너무 오랜만에 이런 문제를 다시 보니 많이 헷갈렸다...

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(bf.readLine());
        for (int x=0; x<tc; x++) {
            int n = Integer.parseInt(bf.readLine());
            HashMap<String, Integer> map = new HashMap<>();
            HashSet<String> set = new HashSet<>();
            for (int i = 0; i<n; i++) {
                String input = bf.readLine();
                String name = input.split(" ")[0];
                String type = input.split(" ")[1];
 
                if (! map.containsKey(type)) {
                    map.put(type, 1);
                } else {
                    map.put(type, map.get(type) + 1);
                }
            }
            List<Map.Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
            List<Integer> sol = new ArrayList<>();
            for (int i=0; i<list.size(); i++) {
                sol.add(list.get(i).getValue());
            }
            System.out.println(solution(sol));
        }
    }
    public static int solution(List<Integer> list) {
        int res = 1;
        for (int i = 0; i < list.size(); i++) {
            res = res * (list.get(i) + 1);
        }
        return res - 1;
    }
}