9375번 - 패션왕 신해빈

1️⃣ Subset

 

✏️ 풀이 과정

부분집합의 개수를 세는 문제가 조금 변형된 형태입니다.

 

부분집합을 출력하는 게 아니라 개수만 세면 되기때문에 간단한 곱셈으로 계산할 수 있습니다.

 

이를 위해서는 옷의 종류가 총 몇 개인지 세야하고 각 종류마다 해당되는 옷이 몇 개인지도 알아야 합니다.

이를 구현하기 위해 HashMap을 통해 종류마다 개수를 등록하고 새로운 종류가 등장할 경우 ArrayList에 추가하여 나중에 for문으로 한 번에 처리하도록 만들었습니다.

 

각 테스트 케이스마다 입력을 받고 나면 1에 종류의 개수만큼 for문을 돌려서 옷의 개수+1 만큼을 각각 곱해줍니다.(해당 종류를 고르지 않는 경우도 포함해야 하기 때문에)

 

그리고 나서 1을 빼주면(아무 것도 없는 경우 제거) 풀이가 완료됩니다.

 

💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

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();
		int n, cnt;
		StringTokenizer st;
		HashMap<String, Integer> map;
		String type;
		ArrayList<String> types;
		for(int t=0;t<T;t++) {
			n = Integer.parseInt(br.readLine());
			cnt = 1;
			map = new HashMap<>();
			types = new ArrayList<>();
			for(int i=0;i<n;i++) {
				st = new StringTokenizer(br.readLine());
				st.nextToken();
				type = st.nextToken();
				map.put(type, map.getOrDefault(type, 0)+1);
				if(map.get(type) == 1) {
					types.add(type);
				}
			}
			for(int i=0;i<types.size();i++) {
				cnt *= (map.get(types.get(i))+1);
			}
			sb.append(cnt-1+"\n");
		}
		System.out.print(sb);
		br.close();
	}
}