[백준] 문자열 폭발 - 9935번

 

문제

 

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

9935번: 문자열 폭발

 

 

 

입력될 수 있는 문자열의 길이가 1,000,000으로 100번만 반복문을 돌아도 1억번의 연산을 하기 때문에 단순한 반복문으로는 시간초과에 부딪힌다.

 

하지만,ㅎㅎ 나는 시간 초과 풀이를 먼저 제출했다ㅎ..

 

munja = input()
target = input()

# 처음부터 스캔하는 방식은 시간초과가 난다.
while True:
    curStart = []
    for i in range(len(munja) - len(target)+1):
        if munja[i:i+len(target)] == target:
            curStart.append(i)
    if len(curStart) == 0:
        break
    for i in curStart:
        munja = munja[:i] + munja[i+len(target):]
        for j in range(len(curStart)):
            if i < curStart[j]:
                curStart[j] -= len(target)
    if munja == '':
        break

if munja == '':
    print("FRULA")
else:
    print(munja)

 

 

한 10퍼정도에서 시간초과가 난다.

 

입력이 백만 정도 된다면, Linear하게 연산을 할 수 있는 다른 방법을 찾아야 한다.

이분탐색..? 밖에 도저히 생각이 안나서, 다른 풀이를 참고해 Stack을 활용한 풀이라는 것을 참고해 다시 풀어보았다.

 

 

stack = []
targetLen = len(target)

for i in range(len(munja)):
    stack.append(munja[i])

    # if len(stack) >= len(target): 아래의 조건문보다 시간이 2배이상 차이남
    if stack[-1] == target[-1]:
        str = ''.join(stack[-targetLen:])
        if str == target:
            for i in range(targetLen):
                stack.pop()

if len(stack) > 0:
    print(''.join(stack))
else:
    print("FRULA")

 

 

주석의 조건문에 따라 실제 실행시간이 2배이상 차이 났고, 조건문의 중요성을 알아간다..

 

stack을 활용한 문제 접근 방법!! 뭔가.. 이젠 조금 알지도..??ㅎ

 

끘~~