[백준] 검열 : 3111 Python

이 문제는 https://congsoony.tistory.com/158 이 블로그를 참고하여 풀었습니다,

위 블로그에서 설명하는 것처럼 문자열 폭발이라는 문제를 먼저 풀고 이문제를 풀면 그나마 쉽게 접근할 수 있다.

이 문제는 앞에서부터 가면서 원하는 단어가 있으면 삭제하고, 뒤에서 부터 탐색하는 과정을 반복한다.

앞에서부터 탐색하는 과정은 문자열 폭발이라는 문제와 동일하다. 스택을 이용하여 끝 문자가 같으면 검사하고 삭제하는 과정을 반복하는 것이다.

뒤에서부터 탐색하는 과정 역시 스택과 비슷하게 큐를 이용하면 같은 로직으로 해결할 수 있다. 

그리고 이를 투포인터를 활용하여 앞에서 진행, 뒤에서 진행 반복하며 모든 문자열을 검사할 때까지 반복했다.

정리하면 아래와 같이 된다.
1. 문자열의 시작을 left, 끝을 right로 시작
2. 앞에서부터 진행하다가 문자열을 제거하면 뒤에서 시작
3. 위 과정을 반복하다가 left > right가 되는 순간 종료

위 과정을 코드로 하면

이렇게 된다.

하지만 여기서 문제가 생기는데 문제에서 주는 테스트 케이스로도 확인 가능하다.

이 예제를 넣고 시작한다면 front 부분에 b, a 가 담기게 되고, back 부분에서 n, a, n, a, d, e, d, a 가 담기게 된다.

이 문제가 왜 발생하는 이유는 앞에서 찾을 때나, 뒤에서 찾을 때는 스택이나 큐를 이용해서 제거한 후에 다시 단어가 만들어지는 경우도 제거할 수 있었다. 하지만 스택에서 찾은 값들과 큐에서 찾은 값들을 합치면서 단어가 만들어지는 경우는 제거하는 로직이 없기 때문에 이런 문제가 생긴 것이다.

다행인 점은 윗부분에서는 모두 제거가 된  상태기 때문에 합친 상태에서 한 번 더 스택을 사용하든, 큐를 사용하든 제거해주면 된다는 것이다.

이렇게 해서 모든 코드를 완성시키면 이렇게 된다.

만약 문자열 폭발이라는 문제를 안 풀어보고 풀었다면 손도 못 댔겠지만, 풀고 풀었기 때문에 손이라도 좀 댈 수 있었다.

백준 문제를 풀 때마다 아직 많이 부족한 것 같다.