[Baekjoon] 9935. 문자열 폭발

문제 설명

문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 “FRULA”를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

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

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, …, 9로만 이루어져 있다.

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

예제 입력 1

mirkovC4nizCC44
C4

예제 출력 1

mirkovniz

예제 입력 2

12ab112ab2ab
12ab

예제 출력 2

FRULA

출처

Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #5 3번

• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: chan4928
• 시간 제한을 수정한 사람: jh05013
• 데이터를 추가한 사람: mrseos

알고리즘 분류

• 자료 구조
• 문자열
• 스택

문제 풀이

# Stack

스택 자료구조를 이용하는 문제입니다.

풀이 과정

이 문제에 대한 가장 단순한 풀이법은 문자열 메소드인 replace() 또는 split() & join()을 사용하는 방법일 것입니다.

하지만 그렇게 풀이하면 문제의 제한 시간을 맞출 수 없습니다.

조금 더 생각해보면 앞에서부터 연속된 문자열을 지우는 것이기 때문에, 스택 자료구조를 사용할 수 있겠다는 생각을 할 수 있습니다.

코드가 직관적이기 때문에 전체 코드를 보면 이해가 쉬울 것입니다.

전체 코드

전체 코드입니다.

stack = []
string = input()
explode = list(input())
length = len(explode)
for ch in string:
    stack.append(ch)
    if len(stack) >= length and stack[-length:] == explode:
        for _ in range(length):
            stack.pop()
print(''.join(stack) if len(stack) > 0 else 'FRULA')

위 코드에서 stack.pop() 대신 리스트 슬라이싱을 이용하면 시간초과가 발생합니다.

아래 코드는 시간 초과가 발생하는 코드입니다.

stack = []
string = input()
explode = list(input())
length = len(explode)
for ch in string:
    stack.append(ch)
    if len(stack) >= length and stack[-length:] == explode:
        stack = stack[:-length]
print(''.join(stack) if len(stack) > 0 else 'FRULA')

이에 대한 이유는 아래 링크를 참고하시면 이해가 가실 것 같습니다.

• https://www.acmicpc.net/board/view/73096

간단하게 정리하면, python의 slicing 연산은 매번 새로운 객체를 생성하는 O(n) 연산이기 때문에 슬라이싱을 사용하면 시간 복잡도가 O(n^2)이 된다는 내용입니다.

배운 점

• Python의 슬라이싱은 매번 새로운 객체를 생성해내는 O(n) 연산이다.
• 앞에서부터 순차적으로 연속된 패턴을 잡아내는 문제에서는 스택 자료구조를 이용한다.
• 입력 크기와 제한 시간을 고려하여 풀이법을 결정할 수 있다.