백준 9375번: 패션왕 신해빈

https://www.acmicpc.net/problem/9375

해빈이는 한 번 입은 조합의 옷을 다시 입지 않는다.

한 종류의 옷은 하나만 입을 수 있을 때, 옷이 주어졌을 때 해빈이는 몇일 버틸 수 있는가?

 

옷을 입력받을 때, 옷의 이름과 옷의 종류를 같이 입력받는데

이 중에서 옷의 이름은 필요가 없고, 옷의 종류만 입력받아준다.

HashMap을 만들어서 옷의 종류를 Key로, 그 종류 옷의 개수를 Value로 저장했다.

그리고 String배열을 만들어서 '옷의 종류'를 인덱스로 꺼낼 수 있게 했다.

 

내가 힘들었던 부분은 경우의 수를 계산하는 부분이었는데,

1종류만 입을 수도 있고, 2종류만 입을 수도 있고 가진 모든 종류를 다 입을 수도 있다는 말에 너무 현혹되었는데,

해당 종류의 옷을 안입는 다고 생각하고 계산하면 되는 거였다.

예를 들어 모자 2종류 옷이 3종류 있다고 하자. 실제로 계산할 때는 1종류만 입었을 때 + 2 종류 다 입었을 때가 아니라

2종류를 입는 건데 안입는 경우의 수을 추가해서,

즉 모자가 3종류(기존 2 종류에 안입는 경우), 옷이 4종류(기존 3 + 안입기)로 생각하면 되는 문제였다.

따라서 모든 (종류의 개수 + 1)의 곱 그리고 아무것도 안입는 경우는 세지 않으므로 -1을 해주면 된다.

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

public class Main {
  static HashMap<String, Integer> hm;
  static String[] categ;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
    int N = Integer.parseInt(br.readLine());
    String output = new String();

    for (int test = 0; test < N; test++) {
      int M = Integer.parseInt(br.readLine());
      hm = new HashMap<>(); 
      categ = new String[31];
      int index = 0;

      for (int i = 0; i < M; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        st.nextToken();
        String name = st.nextToken();
        if (!hm.containsKey(name)) {
          categ[index++] = name;
          hm.put(name, 1);
        }
        else hm.put(name, hm.get(name) + 1);
      }

      int res = 1;
      for (int i = 0; i < index; i++) {
        res *= hm.get(categ[i]) + 1;
      }

      output += (res - 1) + "\n";
    }
    
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    bw.write(output);
    bw.flush();
    bw.close();
  }
}