백준 9375 패션왕 신해빈[Java]⭐

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

풀이

처음 풀이에는 map과 조합을 사용한다.
map에는 map(타입, 해당 타입의 옷 개수)를 저장한다.
2가지 이상의 옷을 고를 경우, 모든 조합의 경우를 구하여 각 조합에 속한 수들을 모두 곱한 값을 cnt에 더한다.
하지만 아래 코드로 풀이한 결과 50%에서 시간 초과가 떴다.

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

public class Main {

    static int cnt;

    public static void combination(int size, int L, int start, ArrayList<Integer> list, int[] comb) {
        if (size == L) {
            int tmp = 1;
            for (int num : comb)
                tmp *= num;
            cnt += tmp;
        }
        else {
            for (int i = start; i < list.size(); i++) {
                comb[L] = list.get(i);
                combination(size, L+1, i+1, list, comb);
            }
        }
    }

    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) {
            int n = Integer.parseInt(br.readLine());
            cnt = 0;
            HashMap<String, Integer> map = new HashMap<>();
            ArrayList<Integer> list = new ArrayList<>();

            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String name = st.nextToken();
                String type = st.nextToken();
                map.put(type, map.getOrDefault(type, 0) + 1);
            }

            //map에 저장된 옷 개수를 list에 저장
            //옷을 1가지만 입는 경우의 수를 cnt에 더함
            for (String type : map.keySet()) {
                int num = map.get(type);
                list.add(num);
                cnt += num;
            }

            int m = list.size();
            //옷을 2~m가지 입는 경우의 수를 cnt에 더하는 재귀함수
            for (int i = 2; i <= m; i++) {
                int[] comb = new int[i];
                combination(i, 0, 0, list, comb);
            }

            sb.append(cnt+ "\n");
        }

        System.out.println(sb);
    }
}

질문 검색을 통해 답을 찾았다.
map을 사용하여 map(타입, 해당 타입의 옷 개수)를 저장하고,
해당 타입의 옷 개수에 1을 더해서 입지 않은 경우까지 고려하고, 각 타입의 옷 개수를 모두 곱해주고 아무것도 입지 않은 경우를 빼주면 된다.

코드

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

public 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) {
            int n = Integer.parseInt(br.readLine());
            HashMap<String, Integer> map = new HashMap<>();

            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String name = st.nextToken();
                String type = st.nextToken();
                map.put(type, map.getOrDefault(type, 0) + 1);
            }

            int cnt = 1;
            for (String type : map.keySet()) {
                int num = map.get(type);
                cnt *= (num+1);
            }
            cnt--;

            sb.append(cnt+ "\n");
        }

        System.out.println(sb);
    }
}

참고: https://st-lab.tistory.com/164