문제 9375 (Java) - 정수, 조합론 문제

 

문제 해설

주어진 데이터를 어떤 자료구조에 저장할지 결정하는 게 중요한 문제

 

문제를 보면 알몸이 아니면 된다고 했으므로 옷 하나만 걸쳐도 문제가 되지 않는다. 결국 옷이 종류별로 몇 개 있는지를 저장하고 옷의 종류별 개수에 1을 더한 결과를 모두 곱한 뒤 1을 빼준다. 1을 더하는 이유는 해당 종류의 옷을 고르지 않는 경우도 있기 때문이고, 모두 곱한 값에 1을 빼주는 이유는 모든 종류의 옷들 중 아무것도 고르지 않은 경우를 빼야 하기 때문이다.

 

 

문제 풀이

어떤 종류의 옷이 있는지 해당 종류의 옷의 개수가 몇개인지를 저장해야 한다. 이에 알맞은 자료구조는 hashmap이다.

옷의 이름은 필요가 없으므로, 옷의 종류가 무엇인지, 해당 종류의 옷이 몇개 있는지를 hashmap에 저장한다.

 

( 해당 옷 종류의 개수 + 1 ) 값을 모두 곱한다. 해당 옷을 고르지 않은 경우 + 해당 옷을 1개 고를 수 있는 경우를 모두 곱해주는 것

 

모두 곱한 값에 -1을 한다. 모든 옷 종류를 하나도 고르지 않은 경우를 빼기 위함이다.

 

결과값 출력 

import java.util.HashMap;
import java.util.Scanner;
import java.util.Set;
 
public class Main {
  public static void main(String []args) {
    Scanner sc = new Scanner(System.in);
    int t;
    t = sc.nextInt();
    for (int i = 0; i < t; i++) {
      int n = sc.nextInt();
      HashMap<String, Integer> map = new HashMap<>();
 
      for (int j = 0 ; j < n ; j++) {
        String first = sc.next();
        String sec = sc.next();
 
        if ( map.containsKey(sec)) {
          int temp = map.get(sec);
          temp += 1;
          map.put(sec, temp);
        } else if (!map.containsKey(sec)) {
          map.put(sec, 1);
        }
 
      }
      int result = 1;
      Set<String> keys = map.keySet();
      for ( String key : keys) {
        int temp = map.get(key);
        result *= (temp+1);
      }
      result -= 1;
      System.out.println(result);
    }
  }
}