[백준] 3111 검열

복기

 

먼저 이 문제는 제가 풀지못한 문제입니다. 결국 다른 사람의 풀이를 보고 풀었죠...ㅜㅜ

 

구슬이 중간에서 터지면 위의 구슬이 떨어져서 밑이랑 색이 같으면 또 터지는 뿌요뿌요 게임처럼 삭제된 문자열 좌우 문자를 붙혀서 A 문자열이 나오면 또 삭제를 해줘야하는 점이 아마 이 문제를 까다롭게 만드는 점인 것 같은데요.

 

먼저, 아래는 다른 사람 풀이를 보고 작성한 코드입니다.

 

 

// 검열
#include <stdio.h>
#pragma warning(disable : 4996)
char A[35], T[300015], s1[300015], s2[300015], b;
int len, l, r, t1, t2;
 
char check(void) {
    if (0 == b) {
        if (t1 < len) return 0;
        for (int i = 1; i <= len; i++) {
            if (s1[t1 - i] != A[len - i]) {
                return 0;
            }
        }
    }
    else {
        if (t2 < len) return 0;
        for (int i = 1; i <= len; i++) {
            if (s2[t2 - i] != A[i - 1]) {
                return 0;
            }
        }
    }
    return 1;
}
int main(void) {
    scanf("%s %s", A, T);
    for (len = 0; A[len]; len++);
    for (r = 0; T[r + 1]; r++);
 
    while (l <= r) {
        if (0 == b) {
            s1[t1++] = T[l++];
            if (s1[t1 - 1] == A[len - 1]) {
                if (check()) {
                    t1 -= len;
                    b ^= 1;
                }
            }
        }
        else {
            s2[t2++] = T[r--];
            if (s2[t2 - 1] == A[0]) {
                if (check()) {
                    t2 -= len;
                    b ^= 1;
                }
            }
        }
    }
    b = 0;
    while (t2) {
        s1[t1++] = s2[--t2];
        if (s1[t1 - 1] == A[len - 1]) {
            if (check())
                t1 -= len;
        }
    }
    s1[t1] = 0;
    return !printf("%s\n", s1);
}// 1

 

위 코드가 제가 맨처음 작성했던 코드와 다른 점은 비교를 앞에서부터 하는가 뒤에서부터 하는가 입니다.

 

글이 좀 애매한데 어떤 의미인가 하면

 

A: aac  T: aaaaaaccc

 

위의 입력이 주어졌을 때, T의 왼쪽에서부터 A 문자열과 일치하는 문자열을 찾는 상황에서

 

앞에서부터 비교한다는건 (a a c 순으로 비교) 아래와 같이 일치하는 문자열을 찾았을 때 인덱스가 4 가 되는 것이고

 

뒤에서부터 비교한다는건 (c a a 순으로 비교) 인덱스가 6 일 때 아래 상황이 되는 겁니다. 

 

aaaa (aac) cc

별 것 아닌 차이 같지만 앞문자부터 비교하면 삭제후 다음 인덱스부터 앞방향 탐색 범위에 삭제 때문에 끊기고 뒤에 남은 문자들이 포함되지 못합니다. 추가로 뭔 짓거리를 더 해줘야 하는 셈이죠. : aaaa (c->) c

 

반면에 뒷문자부터 비교하면 삭제후 다음 인덱스로 옮겨도 버퍼 안의 내용과 비교하면 탐색하던 방향 그대로 뒤에 남은 문자들을 포함해서 비교할 수 있죠 : aaaa (<-c) c

 

물론 전자처럼 구현해도 관계는 없을 겁니다. 하지만, 확실히 후자가 쉬운 길인 것 같네요.

 

// 검열
#include <stdio.h>
#include <string.h>
#pragma warning(disable : 4996)
volatile char A[33], T[300015];
volatile int len, f, r;
 
struct Stack {
    char data[300015];
    int top;
} s1, s2;
void Push(Stack *ps, char in)    { ps->data[ps->top++] = in;    }
char Pop(Stack *ps)                { return ps->data[--(ps->top)];    }
int GetCount(Stack *ps)            { return ps->top; }
 
int main(void) {
    scanf("%s %s", A, T);
    for (len = 0; A[len]; len++);
    for (r = 0; T[r]; r++);
    
    char bSame;
    int n;
    while (r - f >= len) {
        while (r - f >= len) {
            bSame = 1;
            for (int i = 0; i < len; i++) {
                if (T[f + i] != A[i]) {
                    bSame = 0;
                    break;
                }
            }
            if (bSame == 0) 
                Push(&s1, T[f++]);
            else {
                n = GetCount(&s1);
                n = n < len - 1 ? n : len - 1;
                f += len - n;
                for (int i = n - 1; i >= 0; i--)
                    T[f + i] = Pop(&s1);
            }
            while (GetCount(&s2) > 0 && r - f < len) {
                T[r++] = Pop(&s2);
                T[r] = 0;
            }
            if (bSame == 1) break;
        }
        while (r - f >= len) {
            bSame = 1;
            n = r - len;
            for (int i = 0; i < len; i++) {
                if (T[n + i] != A[i]) {
                    bSame = 0;
                    break;
                }
            }
            if (bSame == 0) 
                Push(&s2, T[--r]);
            else {
                n = GetCount(&s2);
                n = n < len - 1 ? n : len - 1;
                r -= len - n;
                T[r] = 0;
                for (int i = n; i > 0; i--)
                    T[r - i] = Pop(&s2);
            }
            while (GetCount(&s1) > 0 && r - f < len) 
                T[--f] = Pop(&s1);
            if (bSame == 1) break;
        }
    }
    while (GetCount(&s1) > 0)
        T[--f] = Pop(&s1);
    while (GetCount(&s2) > 0)
        T[r++] = Pop(&s2);
    T[r] = 0;
    return !printf("%s\n", T + f);
} // 2

 

 

위 코드는 전자 방법으로 푼 코드이고 문자열 삭제후 뒤에 남은 문자랑 비교하려고 (A 문자열 길이 -1) 개 문자를 저장 버퍼에서 빼는... 쓰잘데기 없이 일을 만들어서 하는 방법입니다. 

 

그리고, 사실 이 코드는 틀린 코드입니다. 이유는 잘 모르겠지만 "출력 초과"로 나오네요.. ㅠ_ㅠ

 

'일단 머리좀 식히고 답을 잊을 때쯤 다시와서 틀린 이유를 찾아보자' 는 의미에서 이 코드도 남깁니다.

 

혹여 지나가던 고수님께서 이유를 집어 주신다면 감사할 따름이고요 ㅎㅎ.

 

복기끝

 

 

사실 지금 든 생각이지만 이 것도 시작 문자 한 개만 버퍼랑 비교하고 나머지는 T랑 비교하면 전자나 후자나 다를게 없겠다는 생각이 드네요............. 

지금까지 쓴 글이... ++'