백준 9375: 패션왕 신해빈(java)

문제

---

풀이

 

종류가 A인 의상이 p개, 종류가 B인 의상이 q개, 종류가 C인 의상이 r개 있을 때 가능한 조합은 ((p+1)*(q+1)*(r+1)-1)개이다. 의상이 x개 있을 때 의상을 고를 수 있는 가짓수는 아무 것도 선택하지 않는 경우를 포함하여 (x+1)가지이기 때문이다. 각 카테고리별로 가능한 가짓수를 곱하고, 모든 카테고리에서 의상을 선택하지 않아 옷을 입지 않게 되는 케이스 하나를 제외하면 전체 경우의 수를 구할 수 있다. 위 예제의 첫 번째 테스트 케이스의 경우 headgear에 hat과 turban의 2개, eyewear에 sunglasses의 1개가 있으므로 (2+1)*(1+1)-1=5개이다. 

 

이를 바탕으로, 카테고리 별 의상의 개수를 입력받아 계산하면 끝나는 문제이다. 카테고리와 의상 수를 매치해야 하므로 ㅇ의상의 종류 key와 의상의 개수 value를 저장하는 HashMap을 사용하여 풀이한다.

HashMap<K, V> 클래스

 

BufferedReader와 StringTokenizer를 이용하여 입력 문자열을 분리하고 이를 각각 name과 category에 저장하였다(과정 생략). name은 의상 이름, category는 의상 종류를 저장하는 변수이다. 동일한 이름의 의상이 중복 입력되지 않으므로 딱히 name을 활용할 일은 없지만 일단 저장은 해 주었다.

 

입력된 category가 해시맵에 존재하지 않는 key값이라면(처음 등장한 종류의 의상이라면) 해시맵에 category, 1을 삽입한다. category가 이전에 입력된 적 있는 값이라면, 해당 종류 의상의 개수가 1 증가한 것이므로 해시맵에 category, (기존 category의 의상 개수+1)을 삽입한다. 해시맵에서 key값이 중복될 경우 나중에 삽입된 값으로 덮어쓰기된다는 점을 이용한 것이다.

if(hm.containsKey(category))
	hm.put(category, hm.get(category)+1);
else 
	hm.put(category, 1);

 

이후 HashMap.values() 메소드를 사용하여 각 카테고리별 의상 개수를 구하고 총 경우의 수를 계산하면 된다. 

int noc=1;	//number of cases
for(int count:hm.values()) {
	noc*=(count+1);
}
System.out.println(noc-1);

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
		StringTokenizer st;
		
		int testCase=Integer.parseInt(br.readLine());
		for(int i=0; i<testCase; i++) {
			HashMap<String, Integer> hm=new HashMap<>();	//<종류 개수>
			int n=Integer.parseInt(br.readLine());
			for(int j=0; j<n; j++) {
				st=new StringTokenizer(br.readLine());
				String name=st.nextToken();
				String category=st.nextToken();
				
				if(hm.containsKey(category))
					hm.put(category, hm.get(category)+1);
				else 
					hm.put(category, 1);
			}
			
			int noc=1;
			for(int count:hm.values()) {
				noc*=(count+1);
			}
			System.out.println(noc-1);
		}
	}
}