팬미팅 (난이도 - 상)

1. 문제 설명

(1) 팬미팅에 참가한 M명의 팬들은 줄을 서서 맨 오른쪽 멤버에서부터 시작해 한 명씩 왼쪽으로 움직이며 포옹합니다.

 

(2) 아래의 그림은 행사 과정 일부를 보여줍니다. a~c는 세 명의 하이퍼시니어 멤버이고, 0~4는 다섯 명의 팬들입니다.

(1) 실행 과정

 

(3) 하지만 하이퍼시니의 남성 멤버들이 남성 팬과 포옹하기가 민망하다고 여겨서, 남성 팬과는 포옹 대신 악수를 합니다.

 

(4) 줄을 선 멤버들과 팬들의 성별이 각각 주어질 때 팬미팅이 진행되는 과정에서 하이퍼시니어의 모든 멤버가 동시에 포옹

하는 일이 몇 번이나 있는지 계산하는 프로그램을 만드시오.

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 멤버들의 성별과 팬들의 성별을 각각 나타내는 두 줄의 문자열로 구성한다.

(2) M은 남자, F는 여자를 의미한다.

(3) 맴버의 수와 팬들의 수는 모두 1이상 200,000 이하의 정수이며, 멤버의 수는 항상 팬의 수 이하이다.

 

출력 조건

(1) 멤버들이 동시에 포옹하는 일이 몇 번이나 있는지 출력하시오.

 

 

입력 예제

4

FFFMMM

MMMFFF

FFFFF

FFFFFFFFFF

FFFFM

FFFFFMMMMF

MFMFMFFFMMMFMF

MMFFFFFMFFFMFFFFFFMFFFMFFFFMFMMFFFFFFF

 

출력 예제

1

6

2

2

 

 

 

 

3. 제약 조건

(1) 프로그램은 10초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 한다.

 

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

X

 

 

 

 

6. 코드

: 두 가지 코드가 존재한다.

 

먼저, (1)의 코드처럼 무식하게 접근하는 것이다. 모든 시뮬레이션을 한 번씩 실행시켜 Brute_Force를 수행한다.

 

그러나, (1)의 시간 복잡도는 대략 O(MN-M^2)이 나오게 된다. 그렇게 되면 N과 M이 각각 20만에 달하는 숫자가 나오면 

시간 안에 풀기 어렵다는 것을 알게된다.

 

그래서 우리는 다른 방법으로 두 큰 수를 구하는 알고리즘 즉, 카라츠바 방법을 사용해 보는 것이다. 아래의 그림을 보자.

 

기본적인 카라츠바 계산 공식이다. 이것을 이용할려면 계산 값을 가지고 남성은 1, 여성은 0으로 변환하여 사용한다.

 

그러나, 이것보다 더 간단하게 &연산을 이용하는 방법이 있는데, (2)의 코드를 보고 이해하자.

 

 

(1) Brute Force

public class FanMeeting1 {
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder builder = new StringBuilder();

    private static String M, N;

    public static void main(String[] args) throws Exception{
        int c = Integer.parseInt(sc.readLine());

        for(int i=0; i<c; i++) {
            M = sc.readLine();
            N = sc.readLine();
            builder.append(bruteForce()+"\n");
        }

        System.out.println("\n"+builder);
    }

    private static int bruteForce() {
        int ret = 0;

        for(int i=0; i<N.length() - M.length()+1; i++) {

            // 만약 남성과 남성끼리 만남이 있으면 바로 break와
            // 남성과 남성끼리의 만남이 없으면 바로 ret++를 한다.
            boolean isOk = false;

            for(int j=0; j<M.length(); j++) {
                if((M.charAt(j) == 'M' && N.charAt(j+i) == 'M')) {
                    isOk = false;
                    break;
                }
                isOk = true;
            }
            if(isOk) {
                ret++;
            }
        }
        return ret;
    }
}

 

 

 

 

(2) & 연산을 이용한 알고리즘

public class FanMeeting2 {
	private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
	private static StringBuilder builder = new StringBuilder();
	private static String M,N;
	
	public static void main(String[] args) throws Exception {
		int c = Integer.parseInt(sc.readLine());
		
		for(int i=0; i<c; i++) {
			M = sc.readLine();
			N = sc.readLine();
			builder.append(hugs(M,N)+"\n");
		}
		System.out.println("\n"+builder);
	}
	
	private static int hugs(String M, String N) {
		String strM = M.replace('M', '1').replace('F','0');
		String strN = N.replace('M', '1').replace('F','0');
		
		if(strM.length() > strN.length()) return 0;

		long A = Long.parseLong(strM,2);
		long B = Long.parseLong(strN,2);
		
        int result = 0;

        for(int i=0 ; i < strN.length() - strM.length() + 1 ; i++) {
            if ((A&B) == 0) {
                result += 1;
            }
            
            // 팬을 오른쪽으로 한 칸씩 옮긴다.
            B = (B>>1);
        }

        return result;
	}
}