백준 9935 문자열 폭발 파이썬 풀이

난이도 : 골드4

풀이일 : 2404044

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

9935번: 문자열 폭발

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

오답코드 -> 시간초과

import sys

string = sys.stdin.readline().strip()
target = sys.stdin.readline().strip()
N = len(target)
result = []

for alphabet in string:
    result.append(alphabet)
    if len(result) >= N:
        if result[-N:] == list(target):
            result = result[:-N]

print(''.join(result) if result else "FRULA")

 

틀린 이유

• result = result[:-N] 과정에서 새로운 리스트를 만들고, 재할당하는 과정이 문자열이 길어질수록 비효율적인 코드가 된다. 시간 복잡도록 계산하면 최악의 경우 O(N^2)가 되어 시간초과가 발생한다.

---

풀이코드

import sys

string = sys.stdin.readline().strip()
target = sys.stdin.readline().strip()
N = len(target)
stack = []

for alphabet in string:
    # string 한글자씩 stack 추가
    stack.append(alphabet)
    # stack 마지막 N 글자가 target과 같으면 N만큼 요소 삭제
    if len(stack) >= N and stack[-N:] == list(target):
        for i in range(N):
            stack.pop()

# 리스트에 있는 것들 모아 출력
print(''.join(stack) if stack else "FRULA")

 

배운것

• .strip() : 개행 문자 \n 제거 하고 입력받기
• ''.join() : 공백없이 붙여 출력하기

코드 구성

• stack 방식을 사용하여 마지막 N 개의 글자 비교 후, target과 같은 경우, N개의 글자 pop
• stack이 비어있지 않다면, 공백없이 붙여서 출력한다.

---

코드 개선

import sys

string = sys.stdin.readline().strip()
target = list(map(str, sys.stdin.readline().strip()))
N = len(target)
stack = []

for alphabet in string:
    # string 한글자씩 stack 추가
    stack.append(alphabet)
    # stack 마지막 N 글자가 target과 같으면 N만큼 요소 삭제
    if len(stack) >= N and stack[-N:] == target:
        for _ in range(N):
            stack.pop()

# 리스트에 있는 것들 모아 출력
print(''.join(stack) if stack else "FRULA")

 

코드 변화

• stack의 마지막 N개 요소를 비교할 때, 매번 target을 리스트로 변환하는 대신 처음부터 target을 리스트로 만들었다.

 

맨 아래 코드가 위의 정답 코드, 중간 코드가 해당 부분 수정 코드, 맨 위 코드는 다른 방식으로 수정했던 코드이다.

---

느낀점

• solve.ac를 보니까 내가 문자열 문제는 거의 풀지 않았길래 관련 문제를 골라 풀었다.
• 엄청 오랜만에 푸니까 ''.join도 잊어 버려서 헤맸고, 개행문자 제거는 아예 방법도 모르겠어서 찾아봤다. 역시 문제는 다양하게 풀어야 하나보다 재밌는 문제랑 적응용 문제를 섞어 풀어야지ㅠ