백준_패션왕 신한빈_9375

//알고리즘

1. 자료구조를 활용한 풀이

 -> HashMap 사용 

 

2. 종류마다 옷의 개수를 구해야 하기 때문에

 -> Key 는 옷의 종류인 kind로 하고 개수를 +1 씩 더해서 HashMap에 push

 

3. 경우의 수를 구함

 -> 각 종류의 옷의 개수( n ) + 옷을입지않을경우( 1 ) 

 

4. 경우의 수를 전부 곱합

 

5. 옷을 모두 입지않을 경우를 빼야하기 때문에 결과값 - 1

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

public class 패션왕신해빈_9375 {
	static int n, ans;
	static HashMap<String,Integer> map;

	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 = 1; tc <= T; tc++) {

			n = Integer.parseInt(br.readLine());
			ans = 1;

			map = new HashMap<String,Integer>();

			String name = "";
			String kind = "";

			for (int i = 0; i < n; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				name = st.nextToken();
				kind = st.nextToken();
				
				if(map.get(kind) != null) map.put(kind, map.get(kind)+1);
				else map.put(kind,1); 
			}
			
			for (String str : map.keySet()) {
				 ans *= (map.get(str) +1);
			}
			
			System.out.println(--ans);
		}

	}


}

 

 

※ set과 map을 사용하는 문제를 안풀어봐서 시도해봄.

경우의 수 구하는 기본적인 지식만 있으면 쉽게 구할 수 있음.

처음에 n값이 20까지인 줄 알고 그냥 부분집합을 구하는 재귀함수로 구현했더니 메모리초과가 남.  (n값 최대 30)