Coding Test/baekjoon

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

조용장 2022. 5. 9. 09:17

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

 

9935번: 문자열 폭발

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모

www.acmicpc.net

풀이

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

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

효율적으로 풀 방법을 찾다보니 문제에 같은 문자를 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