[JAVA]백준_9375_패션왕 신해빈

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

9375번: 패션왕 신해빈

 

문제 유형 : 해시를 사용한 집합과 맵

 

풀이 방식

(1) 소스코드 1

부분집합의 경우를 구하여 조건(똑같은 종류가 있을 경우 제외)을 주어서 구현 => 메모리초과

 

(2) 소스코드 2 

경우의 수를 생각

옷의 이름에 상관없이 옷의 종류의 개수만 보면 경우의 수를 계산할 수 있다

공식 = (같은 종류의 의상수 + 1) * (같은 종류의 의상 수 + 1) * ... * (같은 종류의 의상 수 + 1)  - 1  

* 자바 HashMap의 특징 : 중복된 key값은 허용하지 않음, 중복된 값은 갖을 수 있다

 

 

소스코드 1 (메모리 초과)

package BOJ;

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

public class BOJ_9375_패션왕신해빈_Main2 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < T; tc++) {
			int ans = 0;
			int n = Integer.parseInt(br.readLine());
			String[] input = new String[n];
			for (int i = 0; i < n; i++) {
				input[i] = br.readLine();
			}
		
			for (int i = 0; i < (1<<n); i++) {
				HashMap<String, String> map = new HashMap<String, String>();
				boolean flag = true;
loop:			for (int j = 0; j < n; j++) {
					if((i&(1<<j))!= 0){
						StringTokenizer st = new StringTokenizer(input[j]," ");
						String name = st.nextToken();
						String kind = st.nextToken();
						if(map.containsKey(kind)) {
							flag = false;
							break loop;
						}else {
							map.put(kind, name);
						}
					}
				}
				if(flag) ans++;
			}
			System.out.println(ans-1);
		}
		
	}

}

소스코드 2

package BOJ;

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

public class BOJ_9375_패션왕신해빈_Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < T; tc++) {
			int n = Integer.parseInt(br.readLine());
			HashMap<String, Integer> map = new HashMap<String, Integer>();
			for (int i = 0; i < n; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine()," ");
				String name = st.nextToken();
				String kind = st.nextToken();
				if(!map.containsKey(kind)) {
					map.put(kind, 1);
				}else {
					map.put(kind, map.get(kind)+1);
				}
			}
			int ans = 1;
			for (int val : map.values()) {
				ans *= val + 1;
			}
			System.out.println(ans-1);
		}
		
	}

}