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

  • danwoo21
    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);
            BigInteger abcd  = karatsuba(a.add(b), c.add(d));
    
            return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(N)).add(bd.shiftLeft(2*N));
        }
    }
    

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

    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가 되어야 하는 것 아닌가요?


    4년 전
1개의 댓글이 있습니다.
  • 장홍준
    장홍준

    https://algospot.com/forum/read/1923/


    4년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.