문자열 폭발 (9935번) - 백준 (BOJ)

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

9935번: 문자열 폭발

 

백준 - 문자열 폭발 (9935번) (EKSPLOZIJA)

 

난이도 : Gold 4

알고리즘 : Stack

Time Complexity : O( N )

 

import sys
input = sys.stdin.readline


if __name__ == '__main__':
    string = input().rstrip()
    bomb = input().rstrip()
    lb, ls = len(bomb), len(string)
    stack = []
    cur = []
    
    si = 0
    i = 0
    while si < ls:
        if i == lb:
            del cur[-lb:]
            i = stack.pop() if stack else 0
            continue
        if string[si] == bomb[i]:
            i += 1
        else:
            if i and string[si] == bomb[0]:
                stack.append(i)
                i = 1
            else:
                stack = []
                i = 0
        cur.append(string[si])
        si += 1
    
    if i == lb:
        del cur[-lb:]
    print(''.join(map(str, cur)) if cur else 'FRULA')

 

A B A B D A B A B C C

0 1 2
A B C

stack: []

 

"A B A B D A B A B C C" 에서 A B C 를 폭발시켜야 한다.

처음 AB는 같지만 2번 index의 A는 C와 다르다.

 

A B A B D A B A B C C
A B C

 

하지만 A가 A B C의 0번 index인 A와 같으므로,

가장 최근에 일치했던 B의 다음 index인 2을 stack에 저장해둔다.

 

A B A B D A B A B C C
A B C
stack : [2]

 

그리고 이미 0번 index A는 서로 같은 걸 확인했으므로,

0은 건너뛰고 1부터 비교한다.

다시 AB가 일치한다.

 

하지만 2번 index의 C는 D와 다르다.

따라서 다시 0번 index인 A로 돌아간다.

하지만 여전히 A는 D와 다르다.

 

이 경우, 지금까지 쌓아왔던 stack을 빈 list로 초기화한다.

그리고 D의 다음 문자부터, 다시 0번 index부터 비교를 시작한다.

 

stack : []

 

다시 아까와 비슷한 상황이 왔다.

하지만 이번엔 2번 index의 C와 C가 같다.

 

이제 A B C 를 폭발시킬 수 있다.

 

A B A B D A B (A B C) C
A B C
stack : [2]

 

A B C 를 폭발시켰으니, 이제 stack에 남아있는 원소가 있다면 꺼내온다.

2를 꺼내오게 된다.

즉, 2번 index인 C부터 다시 비교하면 된다.

 

A B A B D [A B (A B C) C]
A B C
stack : []

 

2번 index C가 다시 일치한다.

다시 A B C 를 폭발시킨다.

 

이러면 이제 A B C 를 모두 제거한

A B A B D

만 남는다.