7.6 팬미팅

문제

가장 멤버가 많은 아이돌 그룹으로 기네스 북에 올라 있는 혼성 팝 그룹 하이퍼 시니어가 데뷔 10주년 기념 팬미팅을 개최했습니다. 팬미팅의 한 순서로, 멤버들과 참가한 팬들이 포옹을 하는 행사를 갖기로 했습니다. 하이퍼시니어의 멤버들은 우선 무대에 일렬로 섭니다. 팬미팅에 참가한 M명의 핸들은 줄을 서서 맨 오른쪽 멤버에서부터 시작해 한 명씩 왼쪽으로 움직이며 멤버들과 하나씩 포옹을 합니다. 모든 팬들은 동시에 한 명씩 움직입니다.
남성 멤버와 남성 팬이 만났을 때는 포옹 대신 악수를 합니다.
줄을 선 멤버들과 팬들의 성별이 각각 주어질 때 팬미팅이 진행되는 과정에서 하이퍼시니어의 모든 멤버가 동시에 포옹을 하는 일이 몇 번이나 있는지 계산하는 프로그램을 작성하시오.

입력

첫 줄에 테스트 케이스의 개수 C(C<=20)가 주어집니다. 각 테스트 케이스는 멤버들의 성별과 팬들의 성별을 각각 나타내는 두 줄의 문자열로 구성되어 있습니다. 각 문자열은 왼쪽부터 오른쪽 순서대로 각 사람들의 성별을 나타냅니다. M은 해당하는 사람이 남자, F는 해당하는 사람이 여자임을 나타냅니다.
멤버의 수와 팬의 수는 모두 1 이상 200,000 이하의 정수이며, 멤버의 수는 항상 팬의 수 이하입니다.

출력

각 테스트 케이스마다 한 줄에 모든 멤버들이 포옹을 하는 일이 몇 번이나 있는지 출력합니다.

풀이

책에서는 카라츠바 알고리즘을 사용해서 풀었지만 비트 마스크의 and 연산으로 더 간단하게 풀 수 있다.

public static int hugs(String members, String fans) {

        String strA = members.replace('F', '0').replace('M', '1');
        String strB = fans.replace('F', '0').replace('M', '1');

        if (strA.length() > strB.length()) {
            String temp = "";
            temp = strA;
            strA = strB;
            strB = temp;
        }

        int A = Integer.parseInt(strA, 2);
        int B = Integer.parseInt(strB, 2);

        int result = 0;

        for(int i=0 ; i < strB.length() - strA.length() + 1 ; i++) {
            if ((A&B) == 0) {
                result += 1;
            }
            B = (B>>1);
        }

        return result;

    }

#책/종만북