G - Signals
Preview
대회 통계에 따르면 G번 문제는 이번 대회에서 가장 어려웠던 문제 중 하나였습니다. 푼 팀의 수가 적기로도 두 번째 문제였으며, 성공률이 낮기로도 두 번째 문제였습니다. 물론 풀리지 않았던 H번 문제와, J번 문제를 제외한 통계입니다. 방법만 놓고 보면, 결국 모든 경우를 따져보는 것이었기 때문에 그렇게 어렵지는 않은 문제라 할 수 있겠습니다. 하지만 파싱이 들어가는 등, 코딩에 어려운 점들이 다소 있어 대회 때의 타율이 낮지 않았나 생각됩니다.
Problem Description
몇 개의 회로 그림 때문에 어려워 보이기는 하지만, 회로들은 문제 이해를 돕기 위한 설명이었습니다. 문제는 결국 concatination과 or 연산만이 포함된 두 정규식이 주어졌을 때, 각각이 만드는 스트링들의 집합을 비교하는 것이었습니다. 스트링은 알파벳 소문자로만 구성되는데, 예외적으로 1은 null string에 대응됩니다. 두 집합의 비교는 두 집합이 같은지, 혹은 어느 한 쪽이 다른 한 쪽의 부분집합인지, 혹은 두 집합이 disjoint한지를 확인하는 것이었습니다.
Key Observation
이런 식으로 주어진 규칙에 의해 생성되는 대상들을 다루는 문제에서는, 주어진 규칙대로 모든 대상들을 생성해보는 방법을 가장 먼저 떠올릴 수 있습니다. 문제는 시간/공간입니다. 시간이 오래 걸린다거나, 혹은 공간이 많이 필요하다면 이런 식의 방법으로는 문제를 해결할 수 없습니다. 예를 들어 경우의 수를 세는 DP 문제들은, 이런 식으로 모든 대상들을 생성하는 것이 불가능할 때 사용되는 방법입니다. 이 문제에서도 시간이나 공간이 부족하다면 스트링을 매치해보는 식으로 접근해야겠습니다만, 과연 시간과 공간이 어떨까요?
Analysis
먼저 공간을 따져봅시다. 이 문제를 푸는 데 드는 공간은 생성될 수 있는 스트링의 종류에 비례하게 됩니다. 따라서 최대 몇 종류의 스트링이 생성될 수 있는지를 따져봐야 합니다. 먼저 ST와 같은 형태를 살펴봅시다. 이는 S에서 생성되는 스트링에 T에서 생성되는 스트링을 concatinate 하는 경우입니다. 따라서 이 경우에는 |S| * |T|만큼의 스트링이 생성되게 됩니다(|S|는 물론 S에서 생성되는 스트링의 종류 수 입니다). 그렇다면 S|T와 같은 경우는? 이 경우에는 각각에서 생성되는 스트링들 중의 하나이기 때문에, |S|+|T| 만큼의 스트링이 생성되게 됩니다. 물론 각각의 경우에 중복되는 스트링은 제거해야겠지만, 최대로 가능한 경우의 수는 저 정도가 됩니다. 마찬가지 방법으로 따져보면, 스트링을 생성하는 데 필요한 시간도 이와 비슷함을 알 수 있습니다. 물론 각 경우 스트링의 길이가 곱해지는데, 이는 약 50 정도가 곱해진다고 생각할 수 있습니다.
그럼 실제의 제한은 어떻게 될까요? 즉, 가장 많은 종류의 스트링은 어떤 경우에, 얼마만큼 생성될까요? 조금 생각을 해 보면, 더하기들이 여러 번 곱해지는 경우에 가장 많은 스트링이 생성됨을 알 수 있습니다. 즉, (a|b)(a|b)...와 같은 경우가 되는데, 이 경우에는 (a|b)가 최대 10개까지 붙어있을 수 있으므로 2^10 가지의 스트링이 생성됩니다. 하지만 이 경우가 최대는 아닙니다. (a|b|c)가 연달아 붙어 있는 경우, 최대 일곱 개가 붙어있을 수 있으므로 이 때에는 3^7=2187 가지의 스트링이 생성될 수 있습니다. 하지만 (a|b|c|d)와 같은 경우를 따져보면 이 때에는 경우의 수가 줄어든다는 것을 발견할 수 있습니다. 따라서 약 3^7 정도가 최대로 가능한 경우의 수임을 알 수 있습니다. 여기에 스트링의 길이는 50을 곱하면? 충분히 합리적인 시간/공간 제약임을 알 수 있습니다.
하지만 이것이 전부는 아닙니다! 스트링들의 집합을 생성한 후에 이들을 비교해야 하는데, 이 부분에서 오히려 많은 시간이 걸릴 수도 있기 때문입니다. 하지만 따져 봐야 할 집합의 연산들은 두 집합의 크기의 곱 안에 처리할 수 있음을 알 수 있습니다. 즉, 한 쪽 집합의 각 스트링의 대해서, 다른 쪽 집합의 스트링을 하나씩 보면서, 조건이 맞는지를 확인하는 방법이 가능합니다. 이 경우에도 스트링의 길이가 곱해지는데, 2187*2187*50 역시 가능한 범위임을 알 수 있습니다. 물론, 이보다 효율적으로 처리할 수 있는데, 이에 대해서는 뒤에서 다시 언급하겠습니다.
자.. 그럼 이제 남은 것은 스트링들을 직접 생성해보는 방법입니다. 이는 주어진 식을 파싱하고, 파싱하여 나뉜 각 부분에 대해서 스트링을 생성하고, 이들을 합쳐 나가면 됩니다. 말은 쉽지만, 보통 파싱하는 작업은 어렵거나 귀찮겠죠 :p 아마도 여러분들께서는 수식 파싱을 한 번 정도는 해 보셨을 텐데, 이와 비슷한 방법을 이 문제에도 적용할 수 있습니다. 이에 대해서는 자세히 설명하진 않겠습니다 ^^;
여기서는 제가 실제 대회 때 사용했던 재귀 호출을 이용한 방법을 설명하겠습니다. 먼저 각 괄호에 대해서 이와 쌍을 이루는 괄호를 찾습니다. 그리고 각각의 |가 어느 괄호 안에 속해있는지를 찾습니다. 이는 수식을 좌에서 우로 한 번 읽으면서, (가 나올 때마다 stack에 index를 넣고, )가 나올 때마다 빼는 방식으로 해결할 수 있습니다. 이런 식의 자료를 정리한 후에는, 전체 식에 대해서 재귀 함수를 호출합니다.
만약 주어진 식이 ?S의 꼴이라면, 즉 수식 앞에 문자 ?가 하나 붙은 경우라면, S에 대해서 재귀호출을 한 후, 각각의 결과의 앞에 ?에 해당하는 문자를 붙여줍니다. S?와 같은 꼴 역시 이처럼 처리할 수 있습니다. 문자 하나로만 이루어진 수식 역시 간단하게 처리할 수 있고, 문제는 괄호로 수식이 둘러싸인 경우입니다. 이 경우에는 맨 왼쪽 괄호가 어느 괄호와 짝을 이루는지를 찾습니다. 만일 제일 오른쪽 괄호와 짝을 이룬다면, 이는 (S) 와 같은 수식입니다. 이 경우에는 S를 좌에서 우로 읽으면서, 해당 괄호 안에 포함되는 |들을 기준으로 S를 나누고, 나눠진 각 부분에 대해서 재귀호출을 하여 그 결과들을 모두 모으면 됩니다. 맨 왼쪽 괄호가 중간의 괄호와 짝을 이룬다면, 이는 (S)T 와 같은 꼴의 식입니다. 이 경우에는 (S) 에 대해서 재귀호출을 하고, T에 대해서 재귀호출을 한 후에, 각 경우에 생성되는 스트링을 붙여주면 됩니다. 맨 아래에 첨부할 제 소스에서, Go 라는 함수가 이러한 역할을 담당합니다.
다음으로는 두 집합을 비교하는 부분을 살펴 보겠습니다. 만약 두 집합의 원소들에 일관된 순서를 줄 수 있다면, 두 집합을 비교하는 것은 효율적으로 해결할 수 있습니다. 이 문제에서는 집합의 원소들이 스트링이 되므로 C++ STL string의 비교 연산을 이용하여 순서를 줄 수 있습니다.
두 집합이 A, B라는 두 배열(각각 size n, m)에 정렬되어 있다고 했을 때, 만일 A[i] = B[j] 라면, A[i+1] 을 B에서 찾기 위해서는 0~j 의 범위는 살펴볼 필요가 없습니다. 또, 만일 A[i] < B[j] 라면, A[i]를 B에서 찾기 위해서는 j~m의 범위를 살펴볼 필요가 없습니다. 이는 binary search, 혹은 merge sort에서 사용되는 아이디어들인데요, 배열이 정렬되어 있다는 점을 이용하여 탐색 범위를 줄일 수 있게 됩니다. 조금 생각해보시면, 결국 문제에서 사용되는 집합 연산들은 O(n + m)에 해결할 수 있습니다. 물론 스트링의 길이가 곱해져야 하고요.
Source Code
아래는 제가 위에서 설명한 방식을 구현한 소스 코드입니다. 설명에 몇 가지 추가할 부분이 있다면, 먼저 저는 스트링들의 집합을 처리하기 위해서 map 을 이용하였습니다. 사실 set 을 이용해도 됐겠지만, 팀원들이 이런 식으로 쓸 때에는 map이 더 빨랐던 것 같다고 해서.. 또, 1을 처리하기 위해서 저는 빈 스트링 ""를 이용하였습니다. 이는 두 스트링을 concatinate 할 때, ""+s 를 일관되게 쓰기 위해서 입니다. 주의해야 할 점이 있는데, 이 때에는 최종적으로 생성되는 결과에서 ""를 삭제해야 합니다. 이는 어느 한 쪽 집합에 ""가 들어 있지만 다른 쪽에는 들어있지 않을 때, 두 집합이 실제로는 같은데 프로그램은 다르다고 할 수 있기 때문입니다.

#include<cstdio>
#include<string>
#include<map>
#include<stack>
using namespace std;
typedef map<string, int> DT;
typedef map<string, int>::iterator IT;
char *a;
int match[55], belong[55];
DT Go(int l, int r)
{
    DT ret;
    if(l == r)
    {
        if('a' <= a[l] && a[l] <= 'z')
        {
            char s[2];
            s[0] = a[l];
            s[1] = 0;
            ret[string(s)] = 1;
        }
        else
            ret[""] = 1;
    }
    else if(l < r)
    {
        if(a[l] == '1') return Go(l+1, r);
        else if(a[r] == '1') return Go(l, r-1);
        else if('a' <= a[l] && a[l] <= 'z')
        {
            DT temp = Go(l+1, r);
            for(IT it=temp.begin();it!=temp.end();++it)
                ret[a[l] + it->first] = 1;
        }
        else if('a' <= a[r] && a[r] <= 'z')
        {
            DT temp = Go(l, r-1);
            for(IT it=temp.begin();it!=temp.end();++it)
                ret[it->first + a[r]] = 1;
        }
        else if(r == match[l])
        {
            int l1, prev = l;
            for(l1=l;l1<r;l1++)
            {
                if(belong[l1] == l)
                {
                    DT temp = Go(prev+1, l1-1);
                    for(IT it=temp.begin();it!=temp.end();++it)
                        ret[it->first] = 1;
                    prev = l1;
                }
            }
            DT temp = Go(prev+1, l1-1);
            for(IT it=temp.begin();it!=temp.end();++it)
                ret[it->first] = 1;
        }
        else
        {
            DT temp1 = Go(l, match[l]);
            DT temp2 = Go(match[l] + 1, r);
            for(IT it1=temp1.begin();it1!=temp1.end();++it1)
                for(IT it2=temp2.begin();it2!=temp2.end();++it2)
                    ret[it1->first + it2->first] = 1;
        }
    }
    else
    {
        ret[""] = 1;
    }
    return ret;
}
DT Do(char *s)
{
    char str[55];
    sprintf(str,"(%s)",s);
    a = str;
    stack<int> st;
    int l1;
    for(l1=0;l1<strlen(a);l1++)
    {
        match[l1] = belong[l1] = -1;
        if(a[l1] == '(') st.push(l1);
        else if(a[l1] == ')')
        {
            match[l1] = st.top();
            match[st.top()] = l1;
            st.pop();
        }
        else if(a[l1] == '|') belong[l1] = st.top();
    }
    return Go(0, strlen(a) - 1);
}
int equal(DT &a, DT &b)
{
    if(a.size() != b.size()) return 0;
    for(IT it1 = a.begin(), it2 = b.begin();it1 != a.end(); ++it1, ++it2)
    {
        if(it1->first != it2->first) return 0;
    }
    return 1;
}
int subset(DT &a, DT &b)
{
    if(a.size() >= b.size()) return 0;
    IT it1 = a.begin(), it2 = b.begin();
    while(it1 != a.end() && it2 != b.end())
    {
        if(it1->first == it2->first) ++it1, ++it2;
        else if(it1->first > it2->first) ++it2;
        else return 0;
    }
    return (it1 == a.end());
}
int disjoint(DT &a, DT &b)
{
    IT it1 = a.begin(), it2 = b.begin();
    while(it1 != a.end() && it2 != b.end())
    {
        if(it1->first == it2->first) return 0;
        else if(it1->first < it2->first) ++it1;
        else ++it2;
    }
    return 1;
}
int main(void)
{
    int T;
    char str[55];
    for(scanf("%d",&T);T>=1;T--)
    {
        scanf("%s", str);
        DT a = Do(str);
        scanf("%s", str);
        DT b = Do(str);
        a.erase("");
        b.erase("");
        if(equal(a, b)) printf("=");
        else if(subset(a, b)) printf("<");
        else if(subset(b, a)) printf(">");
        else if(disjoint(a, b)) printf("0");
        else printf("1");
        printf("\n");
    }
    return 0;
}

일단 마감에 쫓겨서 여기까지 올리고.. 기회가 되는대로 주석도 달겠습니다 -0-