[백준] 9935 문자열 폭발

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

제한 시간을 고려하여 문자열과 폭발 문자열을 비교하여 스택에 쌓다가 첫 문자열이 일치하면 그 이후 문자들을 비교하여 조건을 처리하는 방식으로 진행하였습니다.

그러나 인덱스 관리의 어려움을 느껴 스택에 문자들을 쌓다가, 마지막 문자가 일치하면 안에 들어온 문자들과 비교하여 모두 일치하면 pop을 시키는 방식으로 접근하였습니다.

2) 알고리즘

• 스택

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

word = list(sys.stdin.readline().strip())       # 주어진 문자열
bomb = list(sys.stdin.readline().strip())       # 폭발 문자열
answer = []                                     # 정답 스택

B = len(bomb)           # 폭발 문자열의 길이
idx = 0                 # 문자열 인덱스
while idx < len(word):
    answer.append(word[idx])        # 현재 문자열을 스택에 넣음

    if word[idx] == bomb[-1]:       # 현재 문자가 폭발 문자열 마지막 문자와 일치하는 경우
        for k in range(1, B+1):     # 폭발 문자열의 길이만큼 반복
            if len(answer) < B:     # 정답에 쌓인 스택의 길이가 폭발 문자열보다 짧은 경우
                break               # 폭발이 무조건 일어나지 않으므로 종료 (인덱스 에러 방지)

            elif answer[-k] != bomb[-k]:    # 중간에 일치하지 않는 문자가 있으면 종료
                break
        else:                       # 모든 문자가 일치한다면
            for k in range(B):      # 해당하는 문자들 삭제
                answer.pop()
    
    idx += 1

if answer:                          # 남은 문자가 있으면 남은 문자열 출력
    print(''.join(answer))
else:
    print('FRULA')

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

문자열의 인덱스 관리에 어려움이 있었습니다.

인덱스 오류가 발생하여 예외 케이스를 찾는데 어려움을 겪었습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

9935번: 문자열 폭발

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다