[G4] 백준 10750번 Censoring C++ 문자열, 스택

리뷰

 

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

대상 문자열에서 특정 문자열을 제외 후 남은 문자열을 출력하는 문제

 

 

전역 변수

• a : 대상 문자열을 저장할 변수
• b : 제외하고자 하는 문자열을 저장할 변수
• c : 대상 문자열에서 특정 문자열을 제외 후 남은 문자열을 저장할 변수

 

함수

없음

 

 

문제풀이

1. a, b를 입력 받고, 변수 n을 a문자열의 크기로, m을 b문자열의 크기로 저장한다.
2. a문자열을 순회하며 c에 a의 현재 인덱스의 문자를 추가한다.
3. c의 크기가 b의 크기 이상일 경우 변수 len을 0, idx를 c의 크기 -1로 저장한다.
4. b를 뒤에서부터 순회하며 c의 idx번째 문자가 b의 j번째 문자와 동일할 경우 len을 증가시키고, idx를 감소시킨다.
5. len과 m이 같을 경우 c에서 len개만큼의 문자를 제거하고, break처리한다.
6. a문자열을 모두 순회할때까지 위 로직을 반복하고 c에 저장된 문자열을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. a는 순방향으로 c에 추가하고, b는 역방향으로 탐색해 줌으로서 탐색을 최대한 줄이려고 했다.
2. a의 문자가 추가될 때마다 탐색이 이루어지므로 제거 후 남은 케이스에 대해서도 탐색이 가능하다.

 

정답 코드

#include<iostream>
using namespace std;

string a, b, c;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> a >> b;
	int n = a.size(), m = b.size();
	for (int i = 0; i < n; ++i) {
		c += a[i];

		if (c.size() >= b.size()) {
			int len = 0;
			int idx = c.size() - 1;

			for (int j = m - 1; j >= 0; --j) {
				if (c[idx] == b[j]) {
					++len;
					--idx;
				}
				if (len == m) {
					while (len--) c.pop_back();
					break;
				}
			}

		}
	}
	cout << c;
}