백준 30463번: K-문자열 Java Solution

1. Problem Definition & Analysis

0부터 9까지 총 $10$가지의 문자가 포함될 수 있는 길이 $10$의 문자열이 $N$개 주어진다. 이 중에서 두 개의 문자열을 순서와 상관없이 선택했을 때 고유한 문자가 $K$개인 경우의 수를 구하는 문제이다. 한 가지 주의해야 할 점은 $N$의 범위가 매우 크기 때문에 4바이트 정수형 범위를 초과할 수 있다는 점이다.

예를 들어 55555555은 고유한 문자가 $1$개이고, 00112233은 고유한 문자가 $4$개이다. 두 문자열을 이어 붙인 5555555500112233은 고유한 문자가 $5$개이다.

000000001이든, 100000000이든, 1111100000이든 1과 0만 사용된다. 그러면 굳이 전체 문자열을 저장할 필요 없이 필요한 데이터만 저장할 수 있다. 여기서 필요한 데이터는 문자열에 어떤 문자(들)이 사용되었는지에 대한 정보이다. 이를 비트마스킹을 활용해 표현한다.

대략적인 로직은 다음과 같다.

1. 사용된 문자의 조합으로 마스크를 생성한다.
2. 마스크를 key로, 사용된 문자 조합의 빈도를 value로 매핑한다.
3. 사용된 문자 조합의 빈도를 바탕으로 경우의 수를 계산한다.

경우의 수를 계산하는 부분은 코드를 통해 이해하는 것이 편할 것이다.

2. Solution

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

class Main {

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;

    public static int N, K;
    public static long result;
    public static long[] count = new long[1 << 10];

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        while (N-- > 0)
            ++count[getMask(br.readLine())];
        for (int m1 = 1; m1 < (1 << 10); m1++)
            for (int m2 = 1; m2 <= m1; m2++)
                if (countBit(m1 | m2) == K)
                    result += m1 == m2
                            ? count[m1] * (count[m2] - 1) / 2
                            : count[m1] * count[m2];
        System.out.println(result);
    }

    public static int getMask(String line) {
        int mask = 0;
        for (char c : line.toCharArray())
            mask |= 1 << (c - '0');
        return mask;
    }

    public static int countBit(int mask) {
        int c = 0;
        for (int i = 0; i < 10; i++)
            if ((mask & (1 << i)) != 0)
                c++;
        return c;
    }
}

전체 코드는 위와 같다. 순서대로 설명해 보겠다.

    public static int getMask(String line) {
        int mask = 0;
        for (char c : line.toCharArray())
            mask |= 1 << (c - '0');
        return mask;
    }

주어진 문자열에서 등장한 문자를 마스킹하는 메서드이다.

        while (N-- > 0)
            ++count[getMask(br.readLine())];

입력받은 문자열을 마스킹한 후 해당 값(= 사용된 문자의 조합)을 키로 사용하여 빈도를 증가시켰다.

        for (int m1 = 1; m1 < (1 << 10); m1++)
            for (int m2 = 1; m2 <= m1; m2++)
                if (countBit(m1 | m2) == K)
                    result += m1 == m2
                            ? count[m1] * (count[m2] - 1) / 2
                            : count[m1] * count[m2];

두 마스크에 OR 연산을 취했을 때 $K$개의 비트가 set되어 있다면(= 두 문자열을 이어 붙였을 때 $K$개의 고유한 문자가 있다면), 문자열 조합의 개수를 계산하는 부분이다.

$(i, j)$ 쌍이 최소한 $i \le j$ 조건을 만족하도록 반복문을 구성했다. 반복문의 $m1 \ge m2$ 조건 덕에 서로 다른 마스크의 경우 빈도 값을 단순히 곱하면 되지만, 같은 마스크의 경우 빈도 값을 단순히 곱하면 중복을 허용하는 순열이 되기 때문에 조합식을 사용해야 한다.

3. Conclusion

다른 복잡한 알고리즘이 병용되지 않으므로 비트마스킹 기법 자체의 응용을 배우기에 매우 좋은 문제라고 생각한다. 해결 방법을 떠올리기까지 그리 오랜 시간이 걸리지 않았는데 막상 글로 옮기려 하니 난해하다는 생각이 든다. 내가 해결한 문제를 온전히 내 것으로 만들기 위해서는 글로도 누구나 이해하기 쉽게 표현할 수 있어야 한다는 생각이 든다.