2009 정보올림피아드 지역본선 문제 Review (5)

시험 당일에 5개의 문제 중 5번을 가장 쉽게 푼 것 같다.

중앙문자열

  문자열에서 교체 연산은 문자열의 한 문자를 다른 문자로 바꾸는 연산이다. 예를 들어, 문자열 “computer”에서 4번째 문자 p를 m으로 교체하면 “commuter”가 된다.
  같은 길이의 두 문자열 P와 Q의 거리 d(P,Q)는 P를 Q로 바꾸기 위한 교체 연산의 최소 개수로 정의된다. 예를 들어 P = “computers”, Q = “consumers”라 하면, P에서 3번째 문자 m을 n으로, 4번째 문자 p를 s로, 6번째 문자 t를 m으로 바꾸면 Q가 된다. 따라서 P와 Q 사이의 거리는 3이다.
  A, B, C를 같은 길이의 문자열이라 하자. 이 때 어떤 문자열 W의 반경 r(W)는 문자열 W와 문자열 A, B, C와의 거리 중 최대값으로 정의된다. 즉, r(W)= max{ d(W,A), d(W,B), d(W,C) } 이다. 예를 들어, A = “computers”, B = “consumers”, C = “consensus”일 때, X = “consunsrs”라 두면, A, B, C와 X 사이의 거리는 d(X,A) = 4, d(X,B) = 2, d(X,C) = 2이므로, X의 반경 r(X)는 4이다.
  문자열 A, B, C의 중앙문자열은 A, B, C와의 반경이 최소가 되는 문자열로 정의된다. 예를 들어, 문자열 A, B, C가 위와 같이 주어졌을 때, Y = “consuners”라 두면, Y의 반경은 3이고, 반경이 2인 문자열은 존재하지 않으므로, Y는 A, B, C의 중앙문자열이 된다.
  영어 소문자들로만 구성된 문자열 A, B, C가 주어졌을 때, 이들의 중앙문자열을 구하는 프로그램을 작성하라.
  실행파일의 이름은 CSTRING.EXE로 하고, 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

입력 형식
  입력 파일의 이름은 INPUT.TXT로 한다. 첫 째 줄에는 문자열 A가 주어진다. 마찬가지로 문자열 B와 C가 각각 둘째 줄과 셋째 줄에 주어진다. 세 문자열의 길이는 동일하고, 그 길이는 1 이상 100,000 이하이다.

출력 형식
  출력 파일의 이름은 OUTPUT.TXT로 한다. 첫 째 줄에 중앙문자열의 반경을 출력하고 둘째 줄에 중앙문자열을 출력한다. 중앙문자열이 여러 개인 경우 하나만 출력한다.

입력과 출력의 예

입력 (INPUT.TXT)

computers
consumers
consensus

출력 (OUTPUT.TXT)

3
consuners

왜 이번에는 그 해법을 잊어버린 것인가... 하고 생각해 보니 예시답안은 맞았지만,
커팅 없이 DFS로 풀었기 때문에 100000글자 테스트에서 1초를 넘겼을 것이라고 짐작했던 기억이 난다.

참고: 위의 조건 computers, consumers, consensus에,
r = 3이 되는 중앙 문자열은 여러 가지가 있다.

• comsuneus
• comsunsrs
• comseners
• conpuneus
• conpunsrs
• conpeners
• consuteus
• consutsrs
• consuners
• conseters
  

이 중 하나를 답으로 낸다면 코드는 정상이다.


당시에 제출했던 코드는 약간 더 최적화가 되어 있지만,
실제 재귀 호출을 이용해 커팅 없는 DFS로 풀면 소스 코드가 어떻게 되나 보자.
시간 복잡도는 3^n이다.

#include <stdio.h>
#include <string.h>
#define MAX(X, Y) (X > Y ? (X) : (Y))

char inputs[3][100001];
char datis[100001];
char optis[100001];
int optii;
int ilen;

void readfile();
void makecstr(int i);
int r(char *w, int len);
int d(char *w, int len, int i);
void writefile();

int main()
{
    readfile();
    makecstr(0);
    writefile();
    return 0;
}

void readfile()
{
    int i;
    FILE* fp;
    fp = fopen("INPUT.TXT", "r");
    for (i = 0; i < 3; i++)
        fscanf(fp, "%s", inputs[i]);
    fclose(fp);
    ilen = strlen(inputs[0]);
    optii = ilen;
}

void makecstr(int i)
{
    if (i < ilen)
    {
        datis[i] = inputs[0][i];
        makecstr(i + 1);
        datis[i] = inputs[1][i];
        makecstr(i + 1);
        datis[i] = inputs[2][i];
        makecstr(i + 1);
    }
    else
    {
        if (r(datis, ilen) < optii)
        {
            strcpy(optis, datis);
            optii = r(datis, ilen);
        }
    }
}

int r(char *w, int len)
{
    return MAX(MAX(d(w, len, 0),d(w, len, 1)),d(w, len, 2));
}

int d(char *w, int len, int i)
{
    int j, c = 0;
    for (j = 0; j < len; j++)
        if (w[j] != inputs[i][j])
            c++;
    return c;
}

void writefile()
{
    FILE* fp;
    fp = fopen("OUTPUT.TXT", "w");
    fprintf(fp, "%d\n%s", optii, optis);
    fclose(fp);
}

3^n이라니.

이 대참사는 문자열을 앞에서부터 완성했기 때문에 벌어진다.
이렇게 푼다면 커팅을 한다 해도 선형시간을 만들 수 없다. 워스트 케이스 때문에...

심사위원들이 컴퓨터를 보고 당황했을 거다.
짧은 문자열에서 답을 내는 프로그램에 긴 문자열을 돌렸더니 거의 멎었을테니.


결론적으로 제대로 풀기 위해서는 DFS를 쓰면 안 된다.
세 문자열에서 같은 자리에 있는 문자들의 관계를 보고 필요한 만큼만 시도해야 하는 것이다.

이 때 세가지 경우가 존재하고 각각에 원칙이 따른다.

1. xxx의 경우. 이 때 최적해에서 이 자리는 무조건 x이다.
2. xxy / xyx / yxx의 경우. 이 때 최적해에서 이 자리는 x가 유리하다.
3. xyz의 경우. 위의 원칙에 따라 만든 후 r이 작아지도록 조정한다.
   r이 충분히 작아지지 않으면 2에서 y를 고를 수 있다.
   

얼핏 보기에는 너무 직관적이어서 코딩하기에는 적절하지 못한 아이디어이다.
하지만 사실 상당히 greedy한 기법이며, 선형 시간 안에 해결 가능하다.
이에 따라 코딩하면 아래와 같이 된다.

#include <stdio.h>
#include <string.h>
#define MAX(X, Y) (X > Y ? (X) : (Y))
#define MIN(X, Y) (X < Y ? (X) : (Y))
#define MAX3(X, Y, Z) MAX(X, MAX(Y, Z))
#define MIN3(X, Y, Z) MIN(X, MIN(Y, Z))

char inputs[3][100001];
char optis[100001];
int ilen;
int d0 = 0, d1 = 0, d2 = 0;

void readfile();
void makecstr();
void writefile();

int main()
{
    readfile();
    makecstr();
    writefile();
    return 0;
}

void readfile()
{
    int i;
    FILE* fp;
    fp = fopen("INPUT.TXT", "r");
    for (i = 0; i < 3; i++)
        fscanf(fp, "%s", &inputs[i]);
    fclose(fp);
    ilen = strlen(inputs[0]);
}

void makecstr()
{
    for (i = 0; i < ilen; i++)
    {
        if (inputs[0][i] == inputs[1][i] &&
            inputs[1][i] == inputs[2][i])
        {
            optis[i] = inputs[0][i];
        }
        else if (inputs[1][i] == inputs[2][i] &&
            inputs[1][i] != inputs[0][i])
        {
            optis[i] = inputs[1][i];
            d0++;
        }
        else if (inputs[2][i] == inputs[0][i] &&
            inputs[2][i] != inputs[1][i])
        {
            optis[i] = inputs[2][i];
            d1++;
        }
        else if (inputs[0][i] == inputs[1][i] &&
            inputs[0][i] != inputs[2][i])
        {
            optis[i] = inputs[0][i];
            d2++;
        }
    }

    for (i = 0; i < ilen; i++)
    {
        if (inputs[0][i] != inputs[1][i] &&
            inputs[1][i] != inputs[2][i] &&
            inputs[2][i] != inputs[0][i])
        {
            if (d2 == MAX3(d0, d1, d2))
            {
                optis[i] = inputs[2][i];
                d0++; d1++;
            }
            else if (d1 == MAX3(d0, d1, d2))
            {
                optis[i] = inputs[1][i];
                d2++; d0++;
            }
            else 
            {
                optis[i] = inputs[0][i];
                d1++; d2++;
            }
        }
    }

    for (i = 0; i < ilen; i++)
    {
        if (MAX3(d0, d1, d2) - MIN3(d0, d1, d2) < 2)
            break;

        if (d0 == MAX3(d0, d1, d2) &&
            inputs[1][i] == inputs[2][i] &&
            inputs[1][i] != inputs[0][i])
        {
            optis[i] = inputs[0][i];
            d1++; d2++; d0--;
        }
        else if (d1 == MAX3(d0, d1, d2) &&
            inputs[2][i] == inputs[0][i] &&
            inputs[2][i] != inputs[1][i])
        {
            optis[i] = inputs[1][i];
            d2++; d0++; d1--;
        }
        else if (d2 == MAX3(d0, d1, d2) &&
            inputs[0][i] == inputs[1][i] &&
            inputs[0][i] != inputs[2][i])
        {
            optis[i] = inputs[2][i];
            d0++; d1++; d2--;
        }
    }
}

void writefile()
{
    FILE* fp;
    fp = fopen("OUTPUT.TXT", "w");
    fprintf(fp, "%d\n%s", MAX3(d0, d1, d2), optis);
    fclose(fp);
}

makecstr() 안에 있는 3개의 for 루프 속 if-else if 순서를 서로 바꿔도 무방하다.
이에 따라 output.txt 안의 답안이 달라질 수 있다.

여기까지.