백준 2825: 수업시간에 교수님 몰래 교실을 나간 상근이

문제 요약

정수 N개가 주어진다. 이때, 친구의 개수를 구하라.

두 수를 이루는 숫자가 적어도 하나 겹치는 쌍을 친구라고 한다. (겹치는 위치는 달라도 된다)

문제 분류

• 수학
• 비트마스킹

문제 풀이

우선 모든 경우를 다 세보는 건 불가능하다. 이 문제를 푸는 핵심은 그룹핑으로 묶어서 경우를 세는 것이다. 우선 어떤 정수를 비트마스킹으로 표현할 수 있다. 각 비트 번호의 숫자가 있으면 1, 없으면 0이다. 그러면 0000000000~1111111111으로 각 수를 표현할 수 있다.
그리고 같은 그룹으로 묶어서 그 개수를 센다. 이러면 O(n) 시간에 카운트 배열을 세고, 그 배열을 이용하여 2^10 * 2^10 정도 시간에 답을 구할 수 있다.
우선 같은 그룹끼리는 친구이므로 같은 그룹에서 2개를 고르는 경우를 센다. (nC2), 그리고 서로 다른 그룹끼리인 경우에, 다른 그룹끼리에서 겹치는 숫자가 있다면 각 그룹의 수를 곱하여 경우의 수를 구한다.

풀이 코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		long visited[] = new long[1 << 10];
		String in;
		long res = 0;
		int cur;
		while(n-- > 0) {
			cur = 0;
			in = br.readLine();
			for(int i = 0; i < in.length(); i++) {
				int bias = in.charAt(i) - '0';
				cur |= 1 << bias;
			}
			visited[cur]++;
		}
		for(int i = 0; i < 1 << 10; i++) {
			res += visited[i] * (visited[i] - 1) / 2;
			for(int j = i + 1; j < 1 << 10; j++)
				if((i & j) > 0) res += visited[i] * visited[j];

		}
		System.out.println(res);
	}
}

추가 풀이

위의 풀이가 정석적인 풀이이지만, 나는 해당 풀이를 찾지 못했다. 나는 본래 n개의 수를 입력받을 때, 즉각 그 친구의 수를 누적할 생각을 했다.
어떤 정수를 비트마스킹으로 표현하고, 그 비트가 하나라도 들어가면 모두 카운팅하는 방식을 사용했다. 즉, 친구 후보수를 하나씩 카운트하고, 입력받은 정수에 대해 친구 후보수를 누적하는 방식이다. 코드는 다음과 같고, 좋은 풀이는 아니다. 시간이 2144ms나 걸렸다.

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		long visited[] = new long[1 << 10];
		String in;
		long res = 0;
		int cur;
		while(n-- > 0) {
			cur = 0;
			in = br.readLine();
			for(int i = 0; i < in.length(); i++) {
				int bias = in.charAt(i) - '0';
				cur |= 1 << bias;
			}
			res += visited[cur];
			for(int i = 0; i < 1 << 10; i++) {
				if((i & cur) > 0)
					visited[i]++;
			}
		}
		System.out.println(res);
	}
}