문제
김상근은 창영마을에서의 권력을 유지하기 위해 신문을 검열하려고 한다.
상근이는 텍스트 T에서 A라는 단어를 다음과 같은 알고리즘을 이용해서 모두 없애려고 한다.
- T에 A가 없으면 알고리즘을 종료한다.
- T에서 처음 등장하는 A를 찾은 뒤, 삭제한다.
- T에 A가 없으면 알고리즘을 종료한다.
- T에서 마지막으로 등장하는 A를 찾은 뒤, 삭제한다.
- 1번으로 돌아간다.
상근이는 마을을 지배해야하기 때문에, 검열을 할 시간이 없다. 상근이의 검열을 대신해주는 프로그램을 작성하시오.
입력
첫째 줄에 단어 A가, 둘째 줄에 텍스트 T가 주어진다. A와 T는 알파벳 소문자로만 이루어져 있고, A는 최대 25자, T는 최대 300,000자이다.
출력
검열을 한 이후의 텍스트를 출력한다.
예제 입력 1
ne
lukanevolisarmu
예제 출력 1
lukavolisarmu
예제 입력 2
aba
ababacccababa
예제 출력 2
bacccab
예제 입력 3
banana
babananananadeda
예제 출력 3
deda
알고리즘 분류
- 구현
- 문자열
- 자료 구조
풀이
처음에는 주어진 조건대로 T의 앞을 검사하고, A가 없다면 false를 return하여 검열을 끝내고, A가 있다면 true를 return하여 이번에는 T의 뒤부터 검사해서 A를 찾고 하는 식으로 했지만 시간 초과가 나서 다른 방법을 찾아보았다.
문자열의 앞 포인터와 뒤 포인터를 변수로 선언하고, 문자열의 앞부터 앞 포인터를 사용해서 검사하며 덱 1에 push_back한다. 검사하는 도중 A가 발견되었다면 A의 길이만큼 덱 1에서 pop_back해준다. 그리고 T의 뒤부터 역순으로 뒤 포인터를 사용해서 검사하며 덱 2에 push_front한다. 검사하는 도중 A가 발견되었다면 A의 길이만큼 덱 2에서 pop_front해준다. 이 과정이 끝나고 T의 앞 포인터가 뒤 포인터를 넘어갔다면 이후부터는 덱 1, 2에서 A를 발견할 수 없을 것이다. 따라서, 마지막으로 덱 1과 2를 합쳐준 후, 다시 A가 있는지 검사하고 있다면 A를 제거한다. 모든 작업이 끝났으면 A를 전부 제거한 T를 출력한다.
이 분이 쓰신 글에 설명이 잘 되어 있다.
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=chogahui05&logNo=221341506848
코드
#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 300000
#define LL long long
#define INF 1e9
using namespace std;
string A, T;
deque<char> DQ_Front;
deque<char> DQ_Back;
int Left_Point, Right_Point;
string answer;
int main() {
FIRST
cin >> A;
cin >> T;
Left_Point = 0;
Right_Point = (T.size() - 1);
while (Left_Point <= Right_Point) { // 문자열의 앞 포인터가 뒤 포인터를 넘어가면 끝
while (Left_Point <= Right_Point) {
DQ_Front.push_back(T[Left_Point++]);
if (DQ_Front.size() >= A.size()) {
bool Flag = true;
int IDX = DQ_Front.size() - 1;
for (int i = (A.size() - 1); i >= 0; i--) {
if (A[i] != DQ_Front[IDX]) {
Flag = false;
break;
}
IDX--;
}
if (Flag) {
for (int i = 0; i < A.size(); i++) {
DQ_Front.pop_back();
}
break;
}
}
};
while (Left_Point <= Right_Point) {
DQ_Back.push_front(T[Right_Point--]);
if (DQ_Back.size() >= A.size()) {
bool Flag = true;
int IDX = 0;
for (int i = 0; i < A.size(); i++) {
if (A[i] != DQ_Back[IDX]) {
Flag = false;
break;
}
IDX++;
}
if (Flag) {
for (int i = 0; i < A.size(); i++) {
DQ_Back.pop_front();
}
break;
}
}
};
};
for (int i = 0; i < DQ_Front.size(); i++) {
answer.push_back(DQ_Front[i]);
}
for (int i = 0; i < DQ_Back.size(); i++) {
answer.push_back(DQ_Back[i]);
}
while (answer.find(A) < MAX) {
answer.erase(answer.find(A), A.size());
};
if (!answer.empty()) {
cout << answer;
}
return 0;
}
'BOJ > Platinum ~ Diamond' 카테고리의 다른 글
[BOJ/Platinum 5] 백준 18891 제21대 국회의원 선거(C++) (0) | 2022.01.31 |
---|---|
[BOJ/Platinum 5] 백준 2505 두 번 뒤집기(C++) (0) | 2022.01.30 |
[BOJ/Platinum 4] 백준 12094 2048 (Hard)(C++) (0) | 2022.01.28 |
[BOJ/Platinum 5] 백준 19235 모노미노도미노(C++) (0) | 2022.01.27 |
[BOJ/Platinum 5] 백준 2642 전개도(C++) (0) | 2022.01.26 |