백준 3111번 검열

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

로직 자체는 백준 9935번 문자열 폭발(https://jaimemin.tistory.com/823)과 똑같은 문제였습니다.

하지만 문자열의 길이가 300,000이기 때문에 O(N^2)으로는 풀 수 없는 문제였습니다.

처음에는 스택으로 접근했는데 TLE가 계속 발생해서 돌핀's 님 블로그(https://dolphins-it.tistory.com/220)를 참고해 덱으로 풀 수 있었습니다.

*덱이 배열처럼 인덱스 접근이 되는지 처음 알았습니다.

#include <iostream>

#include <string>

#include <deque>

#include <algorithm>

using namespace std;

 

const int MAX = 30000;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        string target, s;

        cin >> target >> s;

 

        deque<char> left, right;

        int low = 0, high = s.length() - 1;

 

        while(low <= high)

        {

                 //2번

                 while (low <= high)

                 {

                         bool flag = false;

                         left.push_back(s[low++]);

 

                         if (left.size() >= target.size())

                         {

                                 flag = true;

                                 for(int i=0; i<target.size(); i++)

                                          if (target[i] != left[left.size() - target.size() + i])

                                          {

                                                  flag = false;

                                                  break;

                                          }

                         }

                         if (flag)

                         {

                                 for (int i = 0; i < target.size(); i++)

                                          left.pop_back();

                                 break;

                         }

                 }

                 //4번

                 while (low <= high)

                 {

                         right.push_front(s[high--]);

                         bool flag = false;

                         if (right.size() >= target.size())

                         {

                                 flag = true;

                                 for(int i=0; i<target.size(); i++)

                                          if (target[i] != right[i])

                                          {

                                                  flag = false;

                                                  break;

                                          }

                         }

                         if (flag)

                         {

                                 for (int i = 0; i < target.size(); i++)

                                          right.pop_front();

                                 break;

                         }

                 }

        }

 

        string result;

        for (int i = 0; i < left.size(); i++)

                 result += left[i];

        for (int i = 0; i < right.size(); i++)

                 result += right[i];

 

        //두 덱을 합쳤을 때 나올 수 있는 target 지워주기

        while (result.find(target) < MAX)

                 result.erase(result.find(target), target.size());

       

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~