백준 _ 3111

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

3111번: 검열

문제

---

김상근은 창영마을에서의 권력을 유지하기 위해 신문을 검열하려고 한다.

상근이는 텍스트 T에서 A라는 단어를 다음과 같은 알고리즘을 이용해서 모두 없애려고 한다.

1. T에 A가 없으면 알고리즘을 종료한다.
2. T에서 처음 등장하는 A를 찾은 뒤, 삭제한다.
3. T에 A가 없으면 알고리즘을 종료한다.
4. T에서 마지막으로 등장하는 A를 찾은 뒤, 삭제한다.
5. 1번으로 돌아간다.

상근이는 마을을 지배해야하기 때문에, 검열을 할 시간이 없다. 상근이의 검열을 대신해주는 프로그램을 작성하시오. 

 

 

입력

---

첫째 줄에 단어 A가, 둘째 줄에 텍스트 T가 주어진다. A와 T는 알파벳 소문자로만 이루어져 있고, A는 최대 25자, T는 최대 300,000자이다.

 

출력

---

검열을 한 이후의 텍스트를 출력한다.

 

 

접근법

---

1. 문제에서 보았듯이, 앞에서 먼저 나타내는 A를 지우고, 뒤에서 나타나는 A를 지우는 형태의 문제이다.
2. f_string 과 r_string 의 두개의 스택을 만들어 놓아서 만약 A가 나타난다면, slicing 을 통해 지워주게 된다.(이때, 위치를 알리는fi,ri 를놓아두어 위치를 기록해둔다.)
3. 그 다음, 한가지는 앞 뒤 앞 뒤 해서 계속 지워줬다면, 이제는 앞 뒤가 아닌 , 두개의 stack으로 나눈 배열을 합쳤을때, A 가 나온다면 , 지워주자.
4. 마무리로 ''.join(~) 을 써서 마무리를 해준다.

 

import sys

input = sys.stdin.readline
#rstrip()을 써 오른쪽의 공백을 모두 지워준다.
a = input().rstrip()
revese_a = a[::-1]

t = input().rstrip()
# fi, ri 는 f_st[] 와 r_st[] 의 위치를 모두 가르킨다.
fi,ri = 0,len(t)-1
f_st = []
r_st = []

# 앞에서 넣기, 뒤에서 넣기
while fi <=ri :
	# 앞에서 A 가 나왔을 시 , f_st[-len(a):]을 통한 slicing 을 해준다.
    while fi<=ri:
        f_st.append(t[fi])
        fi+=1
        if len(f_st) >=len(a) and ''.join(f_st[-len(a):]) == a:
            del f_st[-len(a):]
            break
    # 뒤에서 A 가 나왔을 시 , r_st[-len(a):]을 통한 slicing 을 해준다.
    while fi<=ri:
        r_st.append(t[ri])
        ri-=1
        if len(r_st) >= len(a) and ''.join(r_st[-len(a):]) == revese_a:
            del r_st[-len(a):]
            break

all_st = f_st + r_st[::-1]
ti =0
# 최종적으로 all_st 는 f_st와 r_st를 더하여, 그 중 A를 찾아주어 마무리한다.
while ti>=0:
    ti = ''.join(all_st).find(a)
    if ti != -1: 
        del all_st[ti:ti+len(a)]
print(''.join(all_st))