## 팬미팅 문제 시간초과 질문드립니다.

• danwoo21

FANMEETING

다음과 같은 두가지 방법으로 풀어보았는데 둘 다 시간초과가 뜹니다.

다음 코드는 카라츠바 알고리즘을 사용한 풀이입니다.

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int caseN = in.nextInt();
String idol;
String fan;
BigInteger idols;
BigInteger fans;
int count;
for (int i = 0; i < caseN; i++) {
idol = in.next();
fan = in.next();
count = 0;
idol = idol.replaceAll("F", "0");
idol = idol.replaceAll("M", "1");
fan = fan.replaceAll("F",  "0");
fan = fan.replaceAll("M", "1");
idols = new BigInteger(idol);
fans = new BigInteger(fan);
idols = karatsuba(idols, fans);
String zeros = "";
for (int k = idols.toString().length(); k < fan.length(); k++) {
zeros = zeros + "0";
}
zeros = zeros + idols.toString();
for (int j = idol.length() - 1; j < fan.length() ; j++) {
if (zeros.charAt(j) == '0')
count++;
}
System.out.println(count);
}
}
public static BigInteger karatsuba(BigInteger x, BigInteger y) {

// cutoff to brute force
int N = Math.max(x.bitLength(), y.bitLength());
if (N <= 2000) return x.multiply(y);                // optimize this parameter

// number of bits divided by 2, rounded up
N = (N / 2) + (N % 2);

// x = a + 2^N b,   y = c + 2^N d
BigInteger b = x.shiftRight(N);
BigInteger a = x.subtract(b.shiftLeft(N));
BigInteger d = y.shiftRight(N);
BigInteger c = y.subtract(d.shiftLeft(N));

// compute sub-expressions
BigInteger ac    = karatsuba(a, c);
BigInteger bd    = karatsuba(b, d);

}
}


다음은 비트마스킹을 이용한 방법입니다.

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int caseN = in.nextInt();
String idol;
String fan;
BigInteger idols;
BigInteger fans;
int count;
for (int i = 0; i < caseN; i++) {
idol = in.next();
fan = in.next();
count = 0;
idol = idol.replaceAll("F", "0");
idol = idol.replaceAll("M", "1");
fan = fan.replaceAll("F", "0");
fan = fan.replaceAll("M", "1");
idols = new BigInteger(idol,2);
for(int j = 0; j < fan.length() - idol.length() + 1; j++){
fans = new BigInteger(fan.substring(j, j+idol.length()),2);

if (idols.and(fans).compareTo(BigInteger.ZERO) == 0)
count++;
}
System.out.println(count);
}
}
}


idol을 고정시키고 fan 전체를 맞물리게 이동시키면서 and연산 하여
(남자는 1, 여자는 0) 결과가 0일 때만 카운트를 세어 출력하도록
했습니다.

여기서 막혀서 이틀째 고생중인데 도와주세요..

하나 더 질문드리면 책에 있는 카라츠바 알고리즘 코드에서
b의 자릿수가 half보다 작을 때 b0가 b가 되어야 하는 것 아닌가요?

5년 전

• 장홍준