3111. 검열 ( 오답노트 )

문제링크 : https://www.acmicpc.net/problem/3111

먼저 결과만 말하자면 이 문제는 내 힘으로 풀지 못했다. 그래서 잘못 생각한 점, 도움을 받은 방법을 적으려고 한다.

이 문제의 설명은 간단하다.

A, T라는 2개의 문자열이 주어지고

1. T에 A가 없으면 알고리즘을 종료한다.

2. T에서 처음 등장하는 A를 찾은 뒤, 삭제한다.

3. T에 A가 없으면 알고리즘을 종료한다.

4. T에서 마지막으로 등장하는 A를 찾은 뒤, 삭제한다.

5. 1번으로 돌아간다.

이 문제를 보고 시도한 방식은 문제에서 주어진 것과 같다.

1. 문제에서 주어지는 방식대로 T의 맨 앞부터 A가 나올 때까지 탐색을 하고,

2. A가 나올 경우 index를 A의 길이만큼 더한다. ( 새롭게 만들어진 문자열에 추가하지 않음 )

3. 뒤에서부터 A가 나올 때까지 탐색을 하고,

4. A가 나올 경우 index를 A의 길이만큼 뺀다.

코드는 다음과 같다.

- 소스 코드 ( 오답 ) -

#include<iostream>
#include<cstring>
 
using namespace std;
 
char A[27], T[300002];
char front[300002], tail[300002];
 
bool check(int index, int limit, bool direc) {
    if (direc) {
        if (index + strlen(A) -1 > limit) {
            return false;
        }
        else {
            for (int i = 0; i < strlen(A); i++) {
                if (A[i] != T[index + i]) {
                    return false;
                }
            }
        }
        return true;
    }
    else {
        if (index - strlen(A) + 1 < limit) {
            return false;
        }
        else {
            for (int i = index; i > index - strlen(A); i--) {
                if (A[strlen(A) - 1 - (index - i)] != T[i]) {
                    return false;
                }
            }
        }
        return true;
    }
}
 
int main(void) {
    
    cin >> A >> T;
    bool direction = true;
 
    int len_A = strlen(A);
    int len_T = strlen(T);
    int left = 0, right = strlen(T) - 1;
    int front_index = 0;
    int tail_index = 0;
 
 
    while (left <= right) {
        if (direction) {
            if (A[0] == T[left]&&check(left,right,true)) {
                direction = !direction;
                left += len_A;
                printf("앞에 지워짐\n");
            }
            else {
                front[front_index] = T[left];
                front_index++;
                left++;
                printf("앞에 %c 추가됨\n", front[front_index - 1]);
            }
        }
        else {
            if (A[len_A-1] == T[right] && check(right,left,false)) {
                direction = !direction;
                right -= len_A;
                printf("뒤에 지워짐\n");
            }
            else {
                tail[tail_index] = T[right];
                tail_index++;
                right--;
                printf("뒤에 %c 추가됨\n", tail[tail_index - 1]);
            }
        }
        for (int i = 0; i < front_index; i++) {
            printf("%c", front[i]);
        }
        for (int i = tail_index - 1; i >= 0; i--) {
            printf("%c", tail[i]);
        }
        printf("\n");
    }
    for (int i = 0; i < front_index; i++) {
        printf("%c", front[i]);
    }
    for (int i = tail_index - 1; i >= 0; i--) {
        printf("%c", tail[i]);
    }
}
 

내가 작성한 코드에서 잘못된 점은

A : abba

B : abababab(abba)babababa

과 같은 예시에서 처음에 가운데 괄호 안에 있는 abba는 A임을 인식하고 지우지만 abba가 사라지면서 새롭게 만들어진 abba는 인식하지 못하는 것이다. 즉, 이미 지나간 부분의 문자들은 고려 대상에서 제외시켜버린다는 점이다.

이 문제를 어떻게 해결할 지 고민하고 있다가 비슷한 방식으로 문제를 접근한 kdk8361( http://organize-study.tistory.com/102 )님의 조언을 받았다. 탐색을 진행하면서 A라고 인식된 부분이 발견될 경우 A의 길이만큼 인덱스를 다시 빼주면서 확인을 한 것이다. 그렇게 된다면 A가 빠지면서 새롭게 생긴 부분도 확인을 할 수 있게 된다.

※ kdk8361님의 코드는 해당 주소에서 확인할 수 있습니다.

꼭 나중에 다시 풀어봐야할 문제 !!