글 읽기 - 문제 접근 방법

ktjooho 7년 전 0

해당 문제 접근을 양방향 큐(deque)와 이중연결리스트로 접근했는데요.

처음에 T를 처음부터 문자열끝까지 순차적으로 살펴보면서, A의 부분문자열이 있는 곳의 인덱스를 양방향큐에 넣습니다.

큐 양방향에서 데이터를 빼서, 해당 인덱스에 위치하는 문자열을 삭제를 해줍니다.

이 때, 삭제는 T 문자열에 대해서 만든 연결리스트의 정보를 수정해서 문자열을 삭제를 합니다.

대략적으로 이렇게 접근을 했는데, 옳은 방법인가요.??

혹시 모르니 아래에 코드 첨부합니다.

감사합니다!

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <deque>
#include <cstring>
#include <algorithm>

using namespace std;
#define T_SIZE 350000

string s;
deque<int>q;
char a[30],t[T_SIZE];
int l[2][T_SIZE],t_len,a_len,front,back;
bool v[T_SIZE];

int check_visit(int p)
{
    for(int i=1;i<=a_len;++i,p=l[0][p])
        if(v[p] || (a[i]!=t[p]))
            return 1;
    return 0;
}
int visit(int p)
{
    for(int i=1;i<=a_len;p=l[0][p],++i)
        v[p]=1;
    return p;
}
int check_match(int p)
{
    for(int i=1;i<=a_len;++i,p=l[0][p])
    {
        if(p==-1)return 0;
        if(t[p]!=a[i])return 0;
    }
    return 1;
}
int link(int prev, int next)
{
    if(prev==-1||next==-1)return 0;
    if(v[prev]||v[next])return 0;
    l[0][prev]=next;
    l[1][next]=prev;
    return 1;
}
int main()
{
    scanf("%s%s",a+1,t+1);
    t_len = strlen(t+1), a_len = strlen(a+1);
    
    for(int i=1; i<t_len; ++i){
        l[0][i] = i+1;
        l[1][t_len-i+1] = t_len - i;
    }
    
    l[1][1]=l[0][t_len]=-1;
    
    for(int i=1;i<=t_len;++i)
        if(!strncmp(t+i, a+1, a_len))
            q.push_back(i);
    
    for(int s=1;!q.empty();s^=1)
    {
        if(s%2)
        {
            front = q.front();
            q.pop_front();
            if(check_visit(front)){
                s^=1;
                continue;
            }
            int next = visit(front);
            int prev = l[1][front];
            
            if(link(prev, next)){
                for(int i=0; i<a_len-1 && prev != -1; ++i,prev=l[1][prev]){
                    if(check_match(prev))
                        q.push_front(prev);
                }
            }
        }
        else
        {
            back = q.back();
            
            q.pop_back();
            
            if(check_visit(back)){
                s^=1;
                continue;
            }
            
            int next = visit(back);
            
            int prev = l[1][back];
            
            if(link(prev, next)){
                for(int i=0; i<a_len-1 && prev != -1; ++i,prev=l[1][prev]){
                    if(check_match(prev))
                        q.push_back(prev);
                }
            }
        }
    }
    for(int i=1; i<=t_len; ++i){
        if(!v[i]){
            printf("%c",t[i]);
        }
    }

    printf("\n");
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문제 접근 방법

ktjooho 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말