[python] 알고리즘 문제 해결 전략 1권 :: 팬미팅 (ID: FANMEETING)

문제

가장 멤버가 많은 아이돌 그룹으로 기네스 북에 올라 있는 혼성 팝 그룹 하이퍼시니어가 데뷔 10주년 기념 팬 미팅을 개최했습니다. 팬 미팅의 한 순서로, 멤버들과 참가한 팬들이 포옹을 하는 행사를 갖기로 했습니다. 하이퍼시니어의 멤버들은 우선 무대에 일렬로 섭니다. 팬 미팅에 참가한 M명의 팬들은 줄을 서서 맨 오른쪽 멤버에서부터 시작해 한 명씩 왼쪽으로 움직이며 멤버들과 하나씩 포옹을 합니다. 모든 팬들은 동시에 한 명씩 움직입니다. 아래 그림은 행사 과정의 일부를 보여줍니다. a~d는 네 명의 하이퍼시니어 멤버들이고, 0~5는 여섯 명의 팬들입니다.

하지만 하이퍼시니어의 남성 멤버들이 남성 팬과 포옹하기가 민망하다고 여겨서, 남성 팬과는 포옹 대신 악수를 하기로 했습니다. 줄을 선 멤버들과 팬들의 성별이 각각 주어질 때 팬 미팅이 진행되는 과정에서 하이퍼시니어의 모든 멤버가 동시에 포옹을 하는 일이 몇 번이나 있는지 계산하는 프로그램을 작성하세요.

입력

첫 줄에 테스트 케이스의 개수 C (C≤20)가 주어집니다. 각 테스트 케이스는 멤버들의 성별과 팬들의 성별을 각각 나타내는 두 줄의 문자열로 구성되어 있습니다. 각 문자열은 왼쪽부터 오른쪽 순서대로 각 사람들의 성별을 나타냅니다.

M은 해당하는 사람이 남자, F는 해당하는 사람이 여자임을 나타냅니다. 멤버의 수와 팬의 수는 모두 1 이상 200,000 이하의 정수이며, 멤버의 수는 항상 팬의 수 이하입니다.

출력

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

테스트케이스

4
fffmmm
mmmfff
fffff
ffffffffff
ffffm
fffffmmmmf
mfmfmfffmmmfmf
mmfffffmfffmffffffmfffmffffmfmmfffffff

1
6
2
2

나의 답

1. 단순히 계산

def transToInt(tmp_list):
    for i in range(len(tmp_list)):
        if tmp_list[i]=="F"or tmp_list[i]=="f":
            tmp_list[i]=1
        else:
            tmp_list[i]=0
    return tmp_list

def HowMuchHug():
    length = len(mem_list)
    hug_num = 0

    for i in range(len(fan_list)-len(mem_list)+1):
        tmp = 1
        for j in range(i,i+length):
            if not(mem_list[j-i] or fan_list[j]):
                tmp = 0 # 포옹 안 한 사람 있음!
        if tmp==1:
            hug_num+=1
    # 2* 10^(5)

    return hug_num


c = int(input())
result = list()
for _ in range(c):
    mem_list = transToInt(list(input()))
    fan_list = transToInt(list(input()))
    result.append(HowMuchHug())

for obj in result:
    print(obj)

당연히 시간초과

2. 2진수로 변환하여 비트 연산자 사용

def transToInt(l): # 2진수로 변환
    for i in range(len(l)):
        if l[i]=="F":
            l[i]='1'
        else:
            l[i]='0'
    l = ''.join(l)
    return l

c = int(input())
result = list()
for _ in range(c):
    tmp_res = 0
    mem_list = list(input())
    exact_num = pow(2,len(mem_list)) # 나와야하는 수
    mem_num = int(transToInt(mem_list),base=2) # member list를 2진수로 변환
    fan_list = list(input())
    fan_num = transToInt(fan_list)
    for i in range(len(fan_list)-len(mem_list)+1): # O(n-m)
        tmp = (int(fan_num[i:i+len(mem_list)],base=2)|mem_num)+1 # O(m) => 배열 연산자
        if tmp==exact_num:
            tmp_res+=1
    result.append(tmp_res)

for obj in result:
    print(obj)

첫번째는

입력받은 문자열 => 리스트 => 숫자 리스트 => str => int(10진수)

두번째는

10진수가 된 두 수를 & 연산 => +1 => 2의 제곱수인지 확인 (n&(n-1)이 0이면 2의 제곱수)

https://m.blog.naver.com/PostView.nhn?blogId=complusblog&logNo=221204308911&proxyReferer=https%3A%2F%2Fwww.google.com%2F

python의 기본연산자 시간복잡도

이 블로그에 기재된 바에 따르면 l[a:b]와 같이 list에서 일부 구간을 잘라 복사해오는 연산은 O(b-a)의 복잡도를 가지므로, O(n-m)의 for문 안에서 O(m)의 배열 연산자를 사용하면 O(nm-m^2)이 되어 시간 초과가 나온다.

그리고 어차피 저렇게 계산해도 배열의 길이가 20만개 이기 때문에 숫자의 범위가 어떤 자료형으로도 2의 20만승까지 나오므로 저장할 수가 없다. 따라서 문자열 그대로 이용해야한다.

책 해답

책에서와 같이 비트 연산자가 아닌 곱셈으로 접근했어야 for문을 이용할 필요없이 한 번에 계산을 할 수 있고

: O(n-m) => O(1)

곱셈으로 접근했어도 카라츠바 알고리즘을 이용하지 않으면 O(nm)으로 시간초과가 났을 것이다.

결국 카라츠바 알고리즘을 이용한 곱셈으로 문제를 해결해야한다.

곱셈은 다음과 같이 진행된다.

카라츠바 구현해보기

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <chrono>

using namespace std;

void printVector(vector<int>&v1) {
    vector<int>::iterator iter;
    for (iter = v1.begin(); iter != v1.end(); iter++) {
        cout << *iter << " ";
    }
    cout << endl;
}


void normalize(vector<int> &num) {//num[]의 자릿수 올림을 처리한다
    num.push_back(0);
    //자릿수 올림을 처리한다
    for (int i = 0; i < num.size() - 1; i++) //num.size()-1 중요
    {
        if (num[i] < 0)
        {
            int borrow = (abs(num[i]) + 9) / 10;
            num[i + 1] -= borrow;
            num[i] += borrow * 10;
        }
        else
        {
            num[i + 1] += num[i] / 10;
            num[i] %= 10;
        }
    }
    while (num.size() > 1 && num.back() == 0)
        num.pop_back();
}

//두 긴 자연수의 곱을 반환한다
//각 배열에는 각 수의 자릿수가 1의 자리에서부터 시작해 저장되어 있다.
//예:multiply([3,2,1], [6,5,4])=123*456=56088=[8, 8, 0, 6, 5]
vector<int> multiply(const vector<int> &a, const vector<int> &b)
{
    vector<int> c(a.size() + b.size() + 1, 0);
    for (int i = 0; i < a.size(); i++)
        for (int j = 0; j < b.size(); j++)
            c[i + j] += (a[i] * b[j]);
    normalize(c);

    return c;
}

//a+=b*(10^k)를 구현한다
void addTo(vector<int> &a, const vector<int> &b, int k)
{
    int length = b.size();
    a.resize(max(a.size() + 1, b.size() + k));
    for (int i = 0; i< length; i++)
        a[i + k] += b[i]; //이렇게 함으로써 굳이 다른 vector를 선언하지 않아도 되고 간편해졌다
                          //정규화 (+만)             
    for (int i = 0; i < a.size(); i++)
    {
        if (a[i] >= 10)
        {
            a[i + 1] += a[i] / 10;
            a[i] %= 10;
        }
    }
}

//a-=b;를 구현한다 a>=b를 가정한다
void subFrom(vector<int> &a, const vector<int> &b)
{
    int length = b.size();
    a.resize(max(a.size() + 1, b.size()) + 1);

    for (int i = 0; i< length; i++)
        a[i] -= b[i];
    //정규화

    for (int i = 0; i < a.size(); i++)
    {
        if (a[i] < 0)
        {
            a[i] += 10;
            a[i + 1] -= 1;
        }
    }
}

//두 긴 정수의 곱을 반환한다
//(a0+a1)*(b0+b1)=(a0*b0)(=z0)+(a1*b0+a0*b1)(=z1)+(a1*b1)(=z2)의 원리
vector<int> karatsuba(const vector<int> &a, const vector<int> &b)
{
    int an = a.size(), bn = b.size();
    //a가 b보다 짧을 경우 둘을 바꾼다
    if (an < bn)
        return karatsuba(b, a);

    //기저 사례:a나 b가 비어있는 경우
    if (an == 0 || bn == 0)
        return vector<int>();

    //기저 사례:a가 비교적 짧은 경우 O(n^2) 곱셈으로 변경한다
    if (an <= 5)
        return multiply(a, b);

    int half = an / 2;
    //a와 b를 밑에서 half자리와 나머지로 분리한다

    vector<int> a0(a.begin(), a.begin() + half);
    vector<int> a1(a.begin() + half, a.end());
    vector<int> b0(b.begin(), b.begin() + min<int>(b.size(), half));
    vector<int> b1(b.begin() + min<int>(b.size(), half), b.end());

    //z2=a1*b1
    vector<int> z2 = karatsuba(a1, b1);

    //z0=a0*b0
    vector<int> z0 = karatsuba(a0, b0);

    //a0=a0+a1
    //b0=b0+b1

    addTo(a0, a1, 0);
    addTo(b0, b1, 0);

    //z1=(a0+a1)*(b0+b1)-z0-z2
    vector<int> z1 = karatsuba(a0, b0);
    subFrom(z1, z0);
    subFrom(z1, z2);

    //result=z0+z1*10^half+z2*10^(half*2)
    vector<int> result;
    addTo(result, z0, 0);
    addTo(result, z1, half);
    addTo(result, z2, half + half);

    return result;
}



int main(void)

{
    int c;
    cin >> c;
    cin.ignore(256, '\n');
    vector<int> answer;
    vector<int>::iterator iter;
    vector<int> result;

    for (int i = 0; i < c; i++) {
        result.clear();
        answer.push_back(0);

        // string으로 받아서 int형 배열로 변환
        string mem_list;
        string fan_list;
        getline(cin, mem_list);
        getline(cin, fan_list);

        int M = mem_list.size();
        int F = fan_list.size();

        vector<int> arr_m(M), arr_f(F);
        for (int j = 0; j < M; j++) { // 200,000
                                      // M이면 1, F이면 0
            arr_m[j] = (mem_list[j] == 'M');
        }
        for (int j = 0; j < F; j++) { // 200,000
                                      // F는 반대로 저장
            arr_f[j] = (fan_list[F - j - 1] == 'M');
        }

        vector<int> tmp_vector = multiply(arr_m, arr_f);
        result = karatsuba(arr_m, arr_f); // karatsuba 실행
        result.resize(M + F - 1);
        result.resize(result.size()-M+1);

        int k = 0;
        for (int j = result.size()-1; k<=F-M; --j) {
            k++;
            if (result[j] == 0)
                ++answer[i];
        }
    }

    for (iter = answer.begin(); iter != answer.end(); iter++) {
        cout << *iter << endl;
    }
    return 0;

}

https://jaimemin.tistory.com/308 이 블로그의 카라츠바 알고리즘을 응용하여 문제에 맞게 변형해보았다. 사실 카라츠바 알고리즘을 알고리즘 시험 당시에 구현하려면 시간이 너무 오래걸릴 것 같다. (카라츠바를 구현해둔 라이브러리가 없을까..? ㅠ) 따라서 실전에서 쓰기 위해서 큰 수를 곱하는 O(n^log3)의 알고리즘이 있다는 것, 그게 카라츠바 알고리즘 이라는 것을 알아두기만 하면 될 것 같다.

 

그래도 c++ 문법 공부하던 와중에 카라츠바를 구현하게 되어서 문법 공부에 도움이 많이 된 듯하다.

 

*알고스팟의 문제지만 c언어로 풀어서 정답인 사람 외에 정답인 사람이 없는 듯하다. 채점 오류인듯 ㅠㅠ*