백준 9935번 - 문자열 폭발(★★★ / ▲ / 1) : Python

개요

• 풀이 시간 : 30분
• 시간 제한 : 2초(추가 시간 없음)
• 메모리 제한 : 128 MB
• 기출 : Croatian Open Competition in Informatics Contest #5 3번
• 링크 : https://www.acmicpc.net/problem/9935

문제

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

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

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

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

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

입력

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

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

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

출력

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

해결방법

문제 이해하기

이번 문제를 어떻게 풀어야 할지 사실 감이 잡히지 않았다(에휴.. 답도 없다). 그래서 슬쩍 어떻게 푸는가 알고리즘 분류만 확인했다. 그랬더니 스택이 있었다.

진짜 왜 스택을 생각못했을까... 스택을 알고나서는 금방 풀 수 있었다.

알고리즘

1. 스택에다가 주어진 문자열에서 순서대로 하나씩 문자를 넣는다.
2. 폭발 문자열과 스택 맨 위를 비교해서 같다면 제거한다.
3. 반복하면 끝이다.

Python

내 코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    s = input().strip()
    p = input().strip()

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

        if len(stack) >= len(p):
            tmp = "".join(stack[-len(p) :])
            if tmp == p:
                cnt = 0
                while cnt < len(p):
                    stack.pop()
                    cnt += 1

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

맞긴 했지만 시간이 남들과 비교했을때 너무 오래걸렸다. 일단 몇가지 문제점이 있다.

1. while ~ pop 대신에 그냥 del를 해서 제거해주면 된다.
2. len(s), len(p)는 계속해서 작업이 되므로 이를 따로 변수에 저장해주어 사용한다.
3. 마지막으로 핵심!! p의 마지막 문자와 stack의 가장 위와 먼저 비교를 해서 걸려낸다. 그리고 나서 전체 p와 stack을 비교하면 된다. 이게 무슨 소리냐면 밑의 추천 코드를 보자.

추천 코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    s = input().strip()
    p = input().strip()
    n = len(s)
    m = len(p)
    lastChar = p[-1]

    stack = []
    for char in s:
        stack.append(char)
        if char == lastChar and "".join(stack[-m:]) == p:
            del stack[-m:]

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


# 참고 : https://www.acmicpc.net/source/27688706

시간을 비교했을때 대폭 감소한 것을 볼 수 있다.