문제
N명의 참가자와 M개의 영화가 있을 때, 같은 영화 2편을 본 참가자 쌍의 수를 구하라.
입력
첫째 줄에 N, M, 이후 M줄에 (참가자1, 참가자2)가 주어진다.
출력
같은 영화 2편을 본 참가자 쌍의 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 5 1 2 1 3 2 3 1 4 2 4 | 4 |
풀이
각 참가자 쌍이 공통으로 본 영화 수를 BitSet 교집합으로 구하고, 공통 k편에서 C(k,2)를 합산한다.
- 각 참가자별 시청 영화를 BitSet으로 관리한다
- 모든 참가자 쌍에 대해 BitSet AND로 공통 영화 수를 구한다
- 공통 k편이면 C(k,2) = k*(k-1)/2를 답에 더한다
핵심 아이디어: BitSet의 AND 연산으로 공통 영화를 효율적으로 구하고, 조합 공식으로 쌍을 센다.
코드
package day499;
import java.io.*;
import java.util.*;
public class Day472BOJ3096영화제 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
long ans = 0;
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
BitSet[] bs = new BitSet[n + 1];
for (int i = 1; i <= n; ++i) {
bs[i] = new BitSet(1001);
}
for (int i = 1; i <= m; ++i) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
bs[a].set(b);
}
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
BitSet set = new BitSet(1024);
set.or(bs[i]);
set.and(bs[j]);
ans += (set.cardinality() * (set.cardinality() - 1)) / 2;
}
}
bw.write(ans + "");
bw.close();
}
}복잡도
- 시간: O(N² * M/64) - BitSet 연산
- 공간: O(N * M/64)