[골드 IV] 9935번. 문자열 폭발

 문제 

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

9935번: 문자열 폭발

 사용 언어 

Python3

 풀이 과정 

요즘 코딩 테스트를 많이 보며 확실히 느낀 코테 빈출 "문자열" 문제!!

뭔가 이제는 느낌이 다 비슷하다. 저번의 PPAP와 또 비슷한 느낌이었다. 처음엔 나는 저번에 공부한 re 라이브러리를 이용해서 정규식을 써볼까 했는데 문제의 조건을 보니 문자열 길이가 100만까지였다..ㅎㅎ

 

처음 생각한 방식은 단순무식하게 정규표현식 혹은 replace를 사용해서 더이상 폭발할 문자열이 없을 때까지 while문을 돌릴려고 했는데 100만이면 절대 불가능한 방법이었다. 또 시도하면서 알게 된 점은 정규표현식과 replace를 사용할 때 문자열 규칙에는 변수를 사용할 수 없다는 점이었다. bomb_str을 넣으면 절대 문자열 치환이 안돼서 답답했다...

 

그래서 문제 알고리즘 분류 힌트(?)를 봤고 스택이 있길래 스택을 사용해서 풀었다. 그 와중에 최대한 빠르게 하고 싶어서 인덱스로 접근하고 del을 사용했는데 슬라이싱을 피할 순 없었다...

제출했는데 시간이 짧은 편은 아닌 것 같지만 맞았습니다!!

 

 제출 답안 

from sys import stdin
input = stdin.readline

if __name__ == "__main__":
    string = list(input().rstrip())
    bomb_str = list(input().rstrip())
    # 임시 스택에 넣어 비교하기
    tmp = []
    for i in range(len(string)):
        tmp.append(string[i])
        if tmp[-1] == bomb_str[-1] and len(tmp) >= len(bomb_str):
            if tmp[-len(bomb_str):] == bomb_str:
                # for i in range(len(bomb_str)):
                #     tmp.pop()
                del tmp[-len(bomb_str):]
    
    if tmp:
        print("".join(tmp))
    else:
        print("FRULA")

 

 

 다른 사람 코드 

1. 문자열을 list로 변경하지 않고 풀이한 코드

def main():
 
    string = input()    # 전체 문자열
    bomb = input()      # 폭발 문자열
 
    lastChar = bomb[-1] # 폭발 문자열의 마지막 글자
    stack = []
    length = len(bomb)  # 폭발 문자열의 길이
 
    for char in string:
        stack.append(char)
        if char == lastChar and ''.join(stack[-length:]) == bomb:
            del stack[-length:]
 
    answer = ''.join(stack)
 
    if answer == '':
        print("FRULA")
    else:
        print(answer)
 
 
if __name__ == '__main__':
    main()

➡ 나랑 300ms나 차이가 난다. 일단 여러 번 계산해야 하는 것들은 변수에 할당했고 문자열을 list로 변경하지 않고 그대로 접근하면서 join을 사용해 비교했다. join도 시간이 꽤 걸리는 연산으로 알고 있었는데 슬라이싱보다는 짧은걸까? 로직 자체는 비슷해서 아마 그렇다는 결론을... 조심스럽게 내려본다.