[BOJ]9935. 문자열 폭발

문제

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

 

사용 알고리즘

문자열, Stack

 

풀이

고려사항

1. 시간 제한이 까다로운 문제

2. 폭발 이전 문자열과 이후 문자열이 합쳐져서 생긴 새로운 문자열 폭발 여부

 

후기

1. 이 문제의 keypoint는 시간관리이다.

조건 중 '문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.'와 시간은 2초로 추가시간이 주어지지 않았다.

N이 큰 상황에서 최악의 경우 폭발하고 매번 문자열을 순회해야 할 경우 시간 복잡도는 O(N2)이다.

따라서 시간 초과가 예상되었다.

2. 때문에 무조건 입력받은 문자를 한번만 순회하는 방식을 채택했다.

순서대로 스택에 넣으며 현재 문자가 target으로하는 문자의 마지막 문자와 같은 경우에만 확인하는 방법이다.

pop의 경우 조건 상 36이 최대이기 때문에 상수시간으로 처리가 가능했다.

예상 시간복잡도는 O(N)으로 줄어든다.

 

코드

import sys

input = sys.stdin.readline

string = input().rstrip()
target = input().rstrip()

last_target = target[-1]
stack = []

# string을 돌면서 마지막 글자가 일치할 경우에만 폭발여부 확인
for cur in string:
    stack.append(cur)
    if cur == last_target:
        if "".join(stack[len(stack) - len(target) :]) == target:
            for _ in range(len(target)):
                stack.pop()

if stack:
    print("".join(stack))
else:
    print("FRULA")

 

결과