문제
의상 종류별 개수가 주어질 때, 하루에 최소 한 개의 의상을 입는 서로 다른 조합의 수를 구하라.
입력
테스트 케이스 수 T, 각 케이스에 의상 수 N과 의상 정보(이름, 종류)가 주어진다.
출력
각 테스트 케이스마다 서로 다른 의상 조합 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 3 hat headgear sunglasses eyewear turban headgear 1 mask face | 5 1 |
풀이
각 종류별 (개수+1)을 모두 곱한 뒤 1을 빼서 조합 수를 구한다.
- HashMap으로 의상 종류별 개수를 센다
- 각 종류에서 "안 입는 경우"를 포함하여 (개수+1)을 모두 곱한다
- 아무것도 안 입는 경우 1을 빼면 답이다
핵심 아이디어: 각 종류에서 선택지는 (해당 종류 의상 수 + 안 입는 1가지)이므로, 전체 조합은 곱의 법칙으로 구하고 공집합(전부 안 입는 경우)만 제외한다.
코드
package day549;
import java.io.*;
import java.util.*;
public class Day512BOJ9375패션왕 {
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());
while (T-- > 0) {
HashMap<String, Integer> hm = new HashMap<>();
int N = Integer.parseInt(br.readLine());
while (N-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
st.nextToken();
String kind = st.nextToken();
if (hm.containsKey(kind)) {
hm.put(kind, hm.get(kind) + 1);
} else {
hm.put(kind, 1);
}
}
int result = 1;
for (int val : hm.values()) {
result *= (val + 1);
}
sb.append(result - 1).append('\n');
}
System.out.println(sb);
}
}복잡도
- 시간: O(T * N)
- 공간: O(N)