[BOJ]9935(python)

BOJ - 9935(문자열 폭발) python 풀이입니다

어떻게 풀이?

맨 처음에는 bomb 문자 기준으로 split을 하고 그 값을 합쳐 string으로 만들어야겠다고 생각을 했다

하지만 일단 split 자체가 O(n)이 걸리기 때문에 시간이 너무 오래 걸려서 탈락~

다음으로 생각한 방법은 stack을 이용한 방법으로
문자를 하나씩 append해서
폭탄 문자가 만들어질 때 하나씩 제거하는 방식이다

코드

def solution():
    string = input()
    bomb = input()
    length = len(bomb)

    stack = []

    for st in string:
        stack.append(st)
        while len(stack) >= length:
            if ''.join(stack[-length:]) == bomb: 
                for _ in range(length):
                    stack.pop()
            else : break

    answer = ''.join(stack)
    if answer == '':
        answer = 'FRULA'
    
    print(answer)

solution()

• 문자를 하나씩 stack에 append 한다
• stack의 길이가 폭탄 문자의 길이보다 길 때 stack의 맨 뒷자리가 폭탄문자와 같은지를 확인한다
• 같은 경우 stack에서 폭탄 문자를 제거한다
• 이 과정을 반복한다
• stack에 남은 값을 연결해 정답 문자열을 만든다
• stack에 남은 값이 없는 경우 정답을 "FRULA"로 지정한다