[백준] 9375: 패션왕 신해빈

SuKong·2020년 8월 12일
0
post-thumbnail

'9375- 패션왕 신해빈' 문제로 이동!

👉문제

해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?

👉입력

첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.

  • 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.
  • 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.

모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.

예시 -
2
3
hat headgear
sunglasses eyewear
turban headgear
3
mask face
sunglasses face
makeup face

👉출력

각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력하시오.

예시 -
5
3


✍내 풀이

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		int[] ansArr = new int[num];
		for( int i = 0 ; i < num ; i++) {
			int n = sc.nextInt();
			String[][] arr = new String[n][2];
			for( int j = 0 ; j < n ; j++) {
				arr[j][0] = sc.next();
				arr[j][1] = sc.next();
			}
			ansArr[i] = caseNum(arr, n);
		}
		for( int i = 0 ; i < num ; i++) 
			System.out.print(ansArr[i] + " ");
	}	 
	
	static int caseNum(String[][] arr, int num) {
		HashMap<String, Integer> map = new HashMap();
		for( int i = 0 ; i < num ; i++) {
			String clothType = arr[i][1];
			if(map.containsKey(clothType)) 
				map.put(clothType, map.get(clothType)+1);
			else
				map.put(clothType, 1);
		}
		
		int ans = 1;
		for( String key : map.keySet() ) {
			ans = ans * (map.get(key)+1);
		}
		return ans-1;
	}
}


✍Note

  • 분류와 각 분류의 갯수를 짝지어서 저장하기 위해서 => Map 활용
  • 분류를 key로 활용, value로 각 분류의 갯수를 활용

  • 경우의 수 계산 :
    한 분류의 옷의 갯수가 n가지라고 할 때 해당 분류가 옷을 선택할 때 해당 분류에서 어떤옷을 선택하느냐 (n가지) + 옷을 입지 않느냐 (1가지)로 즉 n+1가지의 경우의 수가 나온다.
    즉, map에 저장된 모든 key를 이용해 get한 옷의 갯수(value)에 1을 더해서 서로 곱하면 옷을 고르는 모든 경우의 수를 구할 수 있다.
    위에서 구한 모든 경우의 수에서 아무 옷도 고르지 않은 경우(1가지)를 뺀 값이 최종으로 구하는 리턴값!
profile
안녕하세요 🤗

0개의 댓글