문제 URL : https://www.acmicpc.net/problem/3111
3111번: 검열
첫째 줄에 단어 A가, 둘째 줄에 텍스트 T가 주어진다. A와 T는 알파벳 소문자로만 이루어져 있고, A는 최대 25자, T는 최대 300,000자이다.
www.acmicpc.net
문제 접근법 :
우선 백준의 문자열 폭발 문제를 풀어보라고 권유하고싶습니다.
https://congsoony.tistory.com/108
백준 9935 문자열 폭발
문제URL : https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는
congsoony.tistory.com
아래 문자열 폭발 풀었던 방식인데 기존 문자열을 지우고 또 다시 제거해야하는 문자열이면 또 지워야하니
연속된 문자열 지우는것과 마찬가지로 풀어야합니다.
하지만 이문제는 맨앞에서 먼저일치한것을 제거 그다음에는 맨뒤에서 먼저일치한것을 제거
맨앞에서 제거를할때를 왼쪽에서 제거할때라고 하고 맨뒤에서 제거할때를 오른쪽에서 제거할때라고 하겠스빈다.
이문제를 보면 앞과뒤 여러번 검사를해야하니 투포인터를 자연스럽게 생각해야합니다.
먼저 왼쪽에서 먼저 제거할때는 스택을 이용해야하고 오른쪽에서는 큐를 이용해야합니다.
하지만 stack과 큐를 c++에서 이용할때는 인덱스접근이 힘들기때문에 둘다 deque를 이용해서 푸는게 가장 빠릅니다.
첫번째: 연속적으로 제거할때는 stack을 이용할때는 맨뒤 문자열이 같을때 뒤부터 같은지 확인하고 오른쪽에서 제거할땐
반대로 맨앞에서 같은지 확인해야하겠죠?
두번째 : 투포인터는 기본적으로 l<=r 까지 확인하는게 하는게 기본입니다. 왼쪽오른쪽 제거하나가다보면
두포인터가 만나는 지점까지 문자열을 저장했을때 아직까지는 다제거한것이 아닌
stack 과 큐안에 있는것도 다 더해본후 A라는 문자열이 있는지 확인해야합니다.
세번째 : 왼쪽에서 제거하는 차례일경우 q의 앞에있는 문자열을 스택에 추가합니다. A라는문자열이 나올때까지 나온다면 반대로 스택뒤에있는 문자열을 q의 앞에 문자열에 추가합니다. A라는 문자열이 나올때까지 그렇다면 A의 문자열이 나오면 제거합니다. 이렇게 반복합니다.
네번째 : 그렇다면 어떻게되겠나요? 둘중하나 계속반복하다보면 A라는 문자열이 안나올때 큐나 스택 둘중하나는
사이즈가 반드시 0이되겠죠? 그래서 둘중 사이즈가 있는것을 출력해주면 끝입니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
string A, s;
void input() {
cin >> A;
cin >> s;
}
//왼쪽에서 같은지
bool frontsame(deque<char>& dq) {
int i2 = A.size() - 1;
for (int i = dq.size() - 1; i2 >= 0; i--, i2--) {
if (dq[i] != A[i2])return false;
}
return true;
}
//오른쪽에서 같은지
bool backsame(deque<char>& dq) {
for (int i = 0; i < A.size(); i++) {
if (dq[i] != A[i])return false;
}
return true;
}
//왼쪽에서 제거
void backErase(deque<char>& dq) {
for (int i = 0; i < A.size(); i++)
dq.pop_front();
}
//오른쪽에서 제거
void frontErase(deque<char>& dq) {
for (int i = 0; i < A.size(); i++)
dq.pop_back();
}
void solve() {
deque<char> dq1, dq2;//dq1은 스택 dq2는 큐 라고생각하시면됩니다.
bool flag = true;
int r = 0, l = s.size() - 1;
while (r <= l) {
if (flag) {
dq1.push_back(s[r++]);
if (dq1.back() == A.back() && dq1.size() >= A.size()) {
if (frontsame(dq1)) {
frontErase(dq1);
flag = false;
}
}
}
else {
dq2.push_front(s[l--]);
if (dq2.front() == A.front() && dq2.size() >= A.size()) {
if (backsame(dq2)) {
backErase(dq2);
flag = true;
}
}
}
}
//왼쪽을 제거해야하거나 오른쪽을 제거해나갈때 스택이나 큐는 사이즈가 반드시 0ㅣ
while (dq1.size() != 0 && dq2.size() != 0) {
if (flag) {
dq1.push_back(dq2.front());
dq2.pop_front();
if (dq1.back() == A.back() && dq1.size() >= A.size()) {
if (frontsame(dq1)) {
frontErase(dq1);
flag = false;
}
}
}
else {
dq2.push_front(dq1.back());
dq1.pop_back();
if (dq2.front() == A.front() && dq2.size() >= A.size()) {
if (backsame(dq2)) {
backErase(dq2);
flag = true;
}
}
}
}
string res1(dq1.begin(), dq1.end());
string res2(dq2.begin(), dq2.end());
cout << res1 + res2 << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 논리적인 오류등 어떤질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 19238 스타트 택시 (0) | 2021.08.11 |
|---|---|
| 백준 1948 임계경로 (0) | 2021.08.04 |
| 백준 1865 웜홀 (0) | 2021.07.26 |
| 백준 1520 내리막 길 (0) | 2021.07.26 |
| 백준 2671 잠수함식별 (0) | 2021.07.26 |
