[백준 30573] Clubbing [Java]

문제

http://boj.ma/30573

30573번: Clubbing

 

요약

• 마지막으로 주어진 스케줄 수열에서 N개의 동아리 중 하나 이상의 동아리 구성원 전체를 포함하는 연속 부분 수열의 개수를 구하자.

---

풀이 과정

아이디어

총 N개의 수열(동아리)이 주어졌을 때, 각 연속 부분 수열이 N개의 동아리 중 하나의 모든 원소를 포함하는지를 판단해야 한다.

예제 2 입력은 다음과 같다.

2
baf
lek
affleck

수열 [a, f, f, l, e, c, k] 이 동아리 [b, a, f], [l, e, k] 를 포함하는지 확인하자.

• [b, a, f] : b가 없으므로 어떤 구간도 해당되지 않는다.
• [l, e, k] : 연속 부분 수열 중 leck, fleck, ffleck, affleck 총 4개가 가능하다.

알파벳은 총 17개이지만, 동아리의 개수 N과 스케줄의 길이는 최대 $10^5$이므로 각 구간마다 모든 동아리를 직접 비교하면 시간 초과가 발생한다. 따라서 각 집합을 비트마스크로 표현하여 빠른 포함 관계 판단이 가능하도록 해야한다.

boolean[] covering = new boolean[MAX];
while (N-- > 0) {
    String club = br.readLine();
    int mask = 0;
    for (int i = 0; i < club.length(); ++i) {
        mask |= 1 << (club.charAt(i) - 'a');
    }
    covering[mask] = true;
}
for (int i = 0; i < BIT_COUNT; ++i) {
    for (int mask = 0; mask < MAX; ++mask) {
        if ((mask & (1 << i)) != 0) {
            covering[mask] |= covering[mask ^ (1 << i)];
        }
    }
}

동아리 집합을 포함하는 모든 상위 집합도 해당 동아리를 포함한다고 볼 수 있다.

각 동아리를 하나의 비트마스크로 변환 후 다음과 같이 SOS DP를 수행하자.

 

이제 covering[mask] = true 는 mask가 N개의 동아리 중 하나의 모든 구성원을 포함한다로 확장 가능하다.

이제 스케줄 문자열에서 조건을 만족하는 연속 부분 수열의 개수를 계산하자.

조건을 만족하는 최소 구간으로부터 더 많은 문자를 포함하는 부분 수열을 개수(길이)를 구하자.

while (r < schedule.length) {
    int x = schedule[r] - 'a';
    if (cnt[x]++ == 0) mask |= 1 << x;

    while (l <= r) {
        int y = schedule[l] - 'a';
        int newMask = mask;
        if (cnt[y] == 1) newMask &= ~(1 << y);

        if (!covering[newMask]) {
            break;
        }
        --cnt[y];
        mask = newMask;
        ++l;
    }
    if (covering[mask]) result += l + 1;
    ++r;
}

성능 분석

• 시간 복잡도: $O(17*2^{17}+|S|)$
• 제출결과: Accepted / 236ms / 24860KB

---

참고

문제

http://boj.ma/30573

30573번: Clubbing

 

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/platinum/30573.java

problem-solving/baekjoon-online-judge/platinum/30573.java at main · rogi-rogi/problem-solving