[백준 / BOJ] C++ 3111 검열

3111번: 검열

 

문제

https://www.acmicpc.net/problem/3111

3111번: 검열

 

 

풀이

문자열 T의 왼쪽에서부터 탐색해 문자열 A가 있으면 제거하고, 오른쪽부터 탐색해서 또 있으면 제거, 또다시 왼쪽, 오른쪽,... 반복하며 더 이상 그 문자열 A를 찾을 수 없을 때 남아있는 문자열을 출력하는 문제다.

 

front, back이라는 덱을 2개 사용했다. front는 문자열 T의 앞에서부터 차례대로 넣는 컨테이너고, back은 뒤에서부터 넣는 컨테이너다. 즉, front는 push_back와 pop_back만 이루어지고 back은 push_front와 pop_front만 이루어진다. 넣는 문자열의 인덱스는 left, right로 포인터 두개를 사용해 중복이 되지 않도록 left <= right로 조건을 작성해 줬다.

 

먼저 앞에서부터 A를 찾아야 하므로 front에 T의 문자를 넣는다. 차례대로 넣다가 front의 크기가 A의 크기 이상이면, 가장 최근에 넣은 A 사이즈만큼의 문자를 탐색하며 A와 같은지 검사한다. 이때 인덱싱으로 값을 참고할 수 있기 때문에 덱을 사용했다. 만약 A와 같다면 문자열을 찾았으므로 A의 크기만큼 pop_back을 해주고 반복문을 종료한다. A와 같지 않다면 다음 문자를 넣고 또다시 검사하는 과정을 반복한다.

 

앞에서부터 찾을 때 A를 찾았다면 이제 뒤에서부터 찾을 차례다. back에 넣는다는 점만 빼곤 같은 과정을 거친다. 이를 left <= right 인 동안(모든 문자열을 탐색할 때까지) 반복한다.

 

만약 back에서도 찾았을 경우 다시 front에서 찾을 차례인데, 앞서 지운 문자열 때문에 원래 이어지지 않았던 문자들이 이어지게 된다. 이때 덱에 문자가 push 되고 또 검사를 하며 문자열을 찾을 수 있다.

 

문자열 전체를 탐색한 후, front와 back에는 찾고자 하는 문자열 A가 존재할 수 없다. 하지만 둘을 합쳤을 경우 A가 생길 수 있기 때문에 둘을 합친 다음 A가 있는지 확인한다. 만약 A가 있으면 지워주고 또 생길 수 있으니 있다면 계속해서 지워준다. 그러면 남는 것은 우리가 원하는 답이 된다.

 

처음엔 왼쪽, 오른쪽을 끝낸 다음 각 덱의 문자들을 합쳐 문자열을 만들고 다시 탐색하는 과정을 반복했는데 이러면 시간초과가 나더라. 그래서 많은 시행착오 끝에 혹시나 싶어서 해본 방법(합쳐서 마지막에 반복 돌리는 방법)으로 AC를 받았다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  string A, T;
  cin >> A >> T;
  int left = 0, right = T.size() - 1;
  deque<char> front, back;
  while (left <= right) {
    while (left <= right) {
      front.push_back(T[left]);
      left++;
      int flag = 0;
      if (front.size() >= A.size()) {
        flag = 1;
        for (int i = 0; i < A.size(); i++)
          if (front[front.size() - A.size() + i] != A[i]) {
            flag = 0;
            break;
          }
      }
      if (flag) {
        for (int i = 0; i < A.size(); i++)
          front.pop_back();
        break;
      }
    }
    while (left <= right) {
      back.push_front(T[right]);
      right--;
      int flag = 0;
      if (back.size() >= A.size()) {
        flag = 1;
        for (int i = 0; i < A.size(); i++)
          if (back[i] != A[i]) {
            flag = 0;
            break;
          }
      }
      if (flag) {
        for (int i = 0; i < A.size(); i++)
          back.pop_front();
        break;
      }
    }
  }
  T = "";
  for (int i = 0; i < front.size(); i++)
    T += front[i];
  for (int i = 0; i < back.size(); i++)
    T += back[i];
  while (T.find(A) != string::npos)
    T.erase(T.find(A), A.size());
  cout << T << '\n';
  return 0;
}