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

문제

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

입력

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

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

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

출력

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

예제 입력 1

2
3
hat headgear
sunglasses eyewear
turban headgear
3
mask face
sunglasses face
makeup face

예제 출력 1

5
3

나의 풀이

이 문제는 Map<String, Integer>를 사용하는 문제였다. 파이썬으로 푼다고 생각을 하고 딕셔너리를 쓰면 쉬울텐데라는 생각으로 java에도 딕셔너리 같은 구조가 있는지 찾아보았고 Map이라는 구조를 찾았다.

우선 예제 입력에서 문자열로 주어지는 의상을 보면 공백의 앞부분은 문제를 푸는데 전혀 필요가 없고, 공백의 뒷부분의 종류만을 가지고 Map에 key값으로 넣어주면 되었다. Map을 채우는 방법은 우선 Map에 이미 넣으려는 key값이 있는지를 확인하고 있다면 value값을 1 증가 시켜주고, 없다면 value값을 1로 설정하고 새로 Map에 put을 해주면 됩니다.

// clothes라는 Map에 key값이 존재하는지를 확인
if (clothes.containsKey(kindOfClothe)) {
  clothes.put(kindOfClothe, clothes.get(kindOfClothe) + 1);
}
else clothes.put(kindOfClothe,1);

그리고나서는 총 경우의 수를 구하는 공식을 알면 이 문제는 쉽게 풀 수 있다.

// example 1
headgear : 2  =>  총 경우의 수 : (2+1) - 1

// example 2
headgear : 3
eyewear  : 2
face     : 2  =>  총 경우의 수 : (3+1) * (2+1) * (2+1) - 1

위의 예로 보면 공식은 다음과 같다.

(1번 종류의 value + 1) * (2번 종류의 value + 1) * ... * (i번 종류의 value + 1) - 1

각 종류들의 개수에 1을 더한 수들을 모두 곱해주고 마지막에 1을 빼주면 한 가지 이상을 고르고 중복이 되지않는 모든 경우의 수를 구할 수 있다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * 9375번 패션왕 신해빈
 */
public class Baeckjun9375 {
    public static void main(String[] args) throws IOException {
        Map<String,Integer> clothes;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        // 테스트 반복
        for (int i=0; i<t; i++) {
            clothes = new HashMap<>();
            int n = Integer.parseInt(br.readLine());

            // Map에 Key-Value 채워넣기
            for (int j=1; j<=n; j++) {
                String[] clothe = br.readLine().split( " ");
                String kindOfClothe = clothe[1];
                if (clothes.containsKey(kindOfClothe)) {
                    clothes.put(kindOfClothe,clothes.get(kindOfClothe) + 1);
                }
                else clothes.put(kindOfClothe,1);
            }

            // 경우의 수 구하기
            int answer = 1;
            for (Integer val: clothes.values()) {
                answer *= (val + 1);
            }

            System.out.println(answer-1);
        }
    }
}