[백준 9935] 문자열 폭발 - python (solved.ac - 골드 4)

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

9935번: 문자열 폭발

풀이

문제를 보았을때 알수있는 힌트

엄청 단순하게 풀면 시간 초과가 나올것이라는 생각이 들었지만 역시 그렇게 푸니 시간초과가 나왔다.

효율적으로 풀 방법을 찾다보니 문제에 같은 문자를 2개 이상 포함 되어있지 않다가 조금의 힌트가 되는 것같다.

한문자씩 리스트에 쌓으면 진행하고 그때 폭발 문자열의 마지막 문자가 같은 경우 그때의 쌓인 문자를 비교해서 같은 경우 제거하는 형식으로 문제를 풀면 답이나온다.

import sys

input = sys.stdin.readline

def main():
    n = input().strip()

    m = input().strip()

    n_list =[]

    for i in range(len(n)):
        n_list.append(n[i])
        if n[i]==m[-1]:
            if "".join(n_list[-len(m):])== m:
                del n_list[-len(m):]

    if "".join(n_list)!="":
        print("".join(n_list))
    else:
        print("FRULA")
    
main()

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon9935.py