[코드트리/INTERMEDIATE HIGH] 겹치지 않는 쌍의 수 (JAVA)

📖 문제

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

💡  풀이 방식

• 비트마스크

1. 각 그룹의 인원정보를 숫자 하나로 표현하며, 비트마스크를 이용해 인원 수를 새롭게 추가한다.

arr[i] ^= (1 << num);

 

 

2. 완전탐색을 통해 그룹 2개를 고르고, 이 두 그룹이 겹치지 않으려면 AND(&) 비트 연산 결과가 0이어야 한다. 그럴 때만 정답 갯수 +1을 한다. (시간 복잡도 : O(N^@2))

int cnt = 0;

for(int i = 0 ; i < N - 1 ; i++) {
    for(int j = i + 1 ; j < N ; j++) {
        if((arr[i] & arr[j]) == 0) {	// 두 집합의 & 비트 연산 결과가 0일 때 겹치지 않음
            cnt++;
        }
    }
}

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
 
        for(int i = 0 ; i < N ; i++) {
            String[] str = br.readLine().split(" ");
            int m = Integer.parseInt(str[0]);   // 그룹에 속하는 사람 수
 
            for(int j = 1 ; j <= m ; j++) {
                int num = Integer.parseInt(str[j]);
                arr[i] ^= (1 << num);   // 수 새롭게 추가
            }
        }
 
        int cnt = 0;
        for(int i = 0 ; i < N - 1 ; i++) {
            for(int j = i + 1 ; j < N ; j++) {
                if((arr[i] & arr[j]) == 0) {    // 두 집합의 & 비트 연산 결과가 0일 때 겹치지 않음
                    cnt++;
                }
            }
        }
 
        System.out.println(cnt);
    }
}

---

💦 어려웠던 점

- 비트마스크라고 태그가 안 되어있었다면 혼자서 쉽게 아이디어를 캐치하기는 어려웠을 것 같다.

- 처음에 원소 값을 배열에 일일이 입력받고 저장해서 비교하면서 겹치는지 확인하려고 했는데 (30분 소요), 문제의 의도와 맞지 않다는 것을 깨닫고, 다시 문제의 의도대로 풀었다(+30분 소요).

 

 

1회독	2회독	3회독	4회독	5회독
V