본문 바로가기

Problem Solving/boj

[BOJ] 9935. 문자열 폭발(Python)

 

9935번: 문자열 폭발

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

www.acmicpc.net

 

처음 풀었을 때 시간초과 나서, 다른 분 풀이 보고 스택을 써야한다는 아이디어를 얻어 다시 코딩해서 pass했다.

  • 사용 자료구조 : 문자열 + 스택
  • 코드 설명 아래 주석에 달아놓았다.
  • 핵심 아이디어는
    • 폭발 문자열의 마지막 글자가 현재 탐색하는 문자와 같고,
    • 폭발 문자열과 스택에 폭발 문자열의 길이만큼의 문자열이 같다면,
    • 스택에서 폭발 문자열의 길이만큼 pop() 해준다.
  • 마지막 문자까지 모든 탐색이 끝났을 때,
    • 스택에 남아있는 문자가 있다면 스택을 문자열 형식으로 출력하고,
    • 문자가 남아있지 않다면 "FRULA"를 출력한다.

 

파이썬 코드는 다음과 같다.


from sys import stdin
input = stdin.readline

def solve():
    blen = len(bomb_temp)       # 폭발 문자열의 길이
    last_bomb = bomb_temp[-1]   # 폭발 문자열의 마지막 글자
    stack = []
    for char in temp:
        stack.append(char)
        if char == last_bomb and bomb_temp == stack[-blen:]:
            for _ in range(blen):   # 길이만큼 stack의 문자 삭제
                stack.pop()
    result = ''.join(stack)
    if result:
        return result
    else:
        return "FRULA"			# 남은 문자 없으면

# main
temp = input().strip()                # 전체 문자열
bomb_temp = list(input().strip())     # 폭발 문자열
print(solve())

  • 시간 : 208ms / 메모리 : 185620kb
  • 고찰 : 문자열 문제를 근래에 많이 안 풀어서 이번 주는 문자열 위주로 좀 파야겠다. 문자열은 뭔가 유형이 돌고 도는 문제들이 많으니 좀더 익숙해질 필요가 있겠다.