[Java] BOJ 9375 패션왕 신해빈

문제 

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

• 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다.
• 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다.
• 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?
• 첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.
  • 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.
  • 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다.
  • 같은 종류의 의상은 하나만 입을 수 있다.
• 모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.
• 각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력하시오.

아이디어

• hashmap을 사용하여 옷의 종류를 key값으로 받고 value 값으로는 해당 key값이 기존에 있으면 기존에 있던 value 값에 1을 더한 값을 저장하고 해당 key값이 없다면 1을 저장한다.
• 그리고 저장된 value값들을 가지고 결과값을 계산한다.
• 경우의 수를 모두 곱하면 되는데, value값은 해당 옷 종류가 몇개 있는지 저장한 값이므로 그 value 값에 1을 더한 값을 결과값에 계속 곱해준다. (1을 더하는 이유는 입지 않는다는 선택지도 있으므로 경우가 1 더해지기 때문이다.)
• 그렇게 모든 경우의 수를 곱해주고 난 결과값에 1을 빼준다. (1을 빼주는 이유는 모든 옷 종류를 입지 않는 경우는 빼줘야 되기 때문이다.)

겪은 시행착오

• 처음에는 경우의 수로 계산을 하다가 복잡한 길로 빠져들고 말았다...
• 조합으로 구하는 건가 싶어서 순열, 중복 순열, 조합, 중복 조합들을 찾아봤었다.
• 그렇게 조합으로 풀다가 예제가 통과되길래 제출했는데 틀리고... 반례들을 찾아서 코드를 고쳤는데 계속 틀렸다...
• 결국 코드를 거의 지우고 다시 경우의 수로 접근해서 풀 수 있었다.. ㅜㅜ

처음에 풀었을 때 바로 맞을줄 알았다... ㅜㅜㅜ

계속 틀려도 안될때는 과감하게 코드를 지워서 다시 풀어보는 것도 좋은 방법이다... ㅜ

코드

import java.io.*;
import java.util.*;

public class BOJ9375 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 테스트케이스 개수
        int T = Integer.parseInt(br.readLine());

        for(int test = 0; test < T; test++){
            long n = Integer.parseInt(br.readLine());

            // 옷 종류를 key값으로, 옷 이름을 value 값으로 저장
            HashMap<String, Integer> wear = new HashMap<>();

            if(n == 0){
                sb.append(0 + "\n");
            }
            else{
                for(int i = 0; i < n; i++){
                    StringTokenizer st = new StringTokenizer(br.readLine());

                    // 옷 이름
                    String name = st.nextToken();

                    // 옷 종류
                    String type = st.nextToken();

                    // 만약 hashmap에 입력받은 옷 종류를 key값으로 가지고 있다면
                    // 해당 옷 종류가 이미 한벌이상 들어왔다는 것이므로
                    // 그 옷 종류에 해당하는 value값에 1더해서 저장

                    // hashmap에 key값과 value값 저장
                    wear.put(type, wear.getOrDefault(type,0) + 1);
                }

                // 결과값을 저장할 변수
                int result = 1;

                // hashmap에 저장되어 있는 값들을 가지고 계산
                for(int i : wear.values()){
                    // 각 옷 종류마다 가질 수 있는 경우의 수를 곱해줌
                    // 각 옷 종유마다 가지고 있는 옷의 개수에
                    // 입지 않는다는 선택지도 있으니, 개수에 + 1을 해줌
                    result = result * (i + 1);
                }

                // 모든 옷을 입지 않으면 안되므로
                // 모두 입지 않는 경우를 뺌
                result = result - 1;

                sb.append(result + "\n");
            }
        }
        System.out.println(sb);
    }
}