[python] baekjoon 3111 검열

문제

-> 문제 링크 : https://www.acmicpc.net/problem/3111

3111번: 검열

 

문제풀이

문자열이 최대 30만자이기 때문에 문자열 T에 있는 문자들을 한번씩만 탐색하면서 문제를 해결해야 한다고 생각했다.

문자열 T를 앞에서부터 접근하는 리스트 front와 맨끝에서부터 접근하는 리스트 back을 만들고 한칸씩 이동하면서 새로운 문자가 들어올 때 마다 리스트에 문자열 A가 만들어지는지 검사하면서 나아간다.

만약 리스트 front나 back에 문자열 A가 만들어지면 모두 제거한다.

 

문자열 A는 최대 25자이고 문자열 T는 30만자로 30만 * 25로 제한 시간 안에 문제를 해결할 수 있다.

front와 back이 만나는 순간 모든 문자를 모두 검사한 것이므로 front와 back을 합쳐준다.

이때 주의할 점은 front와 back이 합쳐져서 문자열A가 만들어질 수 있다는 점이다. 

그렇기에 front와 back을 합쳐준 뒤에 문자열 A가 새로 생기는지 테스트해줘야 한다.

ex) 문자열A : ab, front : aaaaaaa, back : bbbbbbb

 

코드

import sys

# 1개
A = sys.stdin.readline().rstrip()
T = sys.stdin.readline().rstrip()
A = list(A)
reverse_A = list(reversed(A))
len_A = len(A)

front = []
back = []

frontIdx = 0
backIdx = len(T)-1

flag = True

while frontIdx <= backIdx :

    if flag :
        front.append(T[frontIdx])
        frontIdx += 1
        if front[-len_A:] == A :
            front[-len_A:] = []
            # front = front[:-len_A] # 주의점 : 이 코드를 사용하면 시간초과가 난다.
            # 위 두 명령어의 시간 차이는 엄청나다.
            # 위에 있는 명령어는 len_A만큼 걸리는거 같은데
            # 밑에 있는 명령어는 아마 front-len_A 만큼 걸리기에 front가 커지면 엄청난 시간이 걸리는 듯
            flag = False

    else :
        back.append(T[backIdx])
        backIdx -= 1

        if back[-len_A:] == reverse_A:
            # back = back[:-len_A]
            back[-len_A:] = []
            flag = True

while back :
    front.append(back.pop())

    if front[-len_A:] == A:
        # front = front[:-len_A]
        front[-len_A:] = []

answer = "".join(front)
print(answer)

초기 접근 방식과 오답의 원인

1. 리스트 front와 back이 합쳐질 때 문자열A가 새로 생기는 부분을 간과하여 계속해서 오답이 발생했다.

2. front = front[:-len_A]와 같은 코드로 문제를 해결하려다 보니 시간초과가 걸렸다.

 

 

코드에 잘못된 부분이나 개선 사항이 있다면 댓글로 알려주시면 감사하겠습니다.