[CLASS 4]백준 9935번 - 문자열 폭발

9935번 - 문자열 폭발

 

솔직히 상당히 쉬운 문제인데 너무 어렵게 접근한 감이 없지않아 있다.

 

먼저 스택을 사용해야 한다는 것만 떠올릴 수 있다면 쉽게 풀 수 있었다.

 

내 코드:

# dawitblog.tistory.com/159

string, explosion = input(),input()
explosion_length = len(explosion)
str_stack,explosion_stack = [],[]
str_pointer = -1

# 폭발 문자열이 하나의 문자일 경우
if len(explosion) == 1:
    string = string.replace(explosion,'')
    print(string if string else 'FRULA')
    exit()

idx_dict = {}
for i in range(explosion_length):
    idx_dict[explosion[i]] = i

for char in string:
    str_stack.append(char)
    explosion_stack.append(char)
    str_pointer += 1
    
    # 폭발 문자열의 첫 문자가 입력된 경우
    if explosion_stack[-1] == explosion[0]:
        str_pointer = 0
    # 폭발 문자열의 마지막 문자가 입력된 경우
    elif explosion_stack[-1] == explosion[-1] and str_pointer == explosion_length - 1:
        for _ in range(explosion_length):
            # 폭발 문자열 제거
            explosion_stack.pop()
            str_stack.pop()
        # 포인터 값 초기화
        if explosion_stack:
            str_pointer = idx_dict[explosion_stack[-1]]
        else:
            str_pointer = -1
    # 폭발 문자열의 중간 문자가 순서에 맞게 입력된 경우
    elif explosion_stack[-1] in explosion and len(explosion_stack) >= 2 and idx_dict[explosion_stack[-2]] + 1 == idx_dict[explosion_stack[-1]]:
        continue
    else:
        # 폭발 스택 초기화, 포인터 값 초기화
        explosion_stack = []
        str_pointer = -1
    

print(''.join(str_stack) if str_stack else 'FRULA')

 

파이썬의 del 키워드를 쓰지 않는다면 이런 대참사가 일어난다. 이렇게 풀 필요는 전혀 없고, del 키워드를 사용하면 훨씬 간단하게 풀 수 있다.

 

suncar1000님의 코드:

def main():
    string = input().strip()
    bomb = input().strip()
    bombl = list(bomb)
    b_last = bomb[-1]
    bl = len(bomb)

    ans = []
    for l in string:
        ans.append(l)
        if b_last == l and bombl == ans[-bl:]:
            del ans[-bl:]

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


if __name__ == '__main__':
    main()

 

풀 때 당시에는 왜 이런 생각을 못했는지 모르겠다.. 리스트 슬라이싱을 통해 스택의 마지막에서 폭발 문자열의 개수 만큼만 잘라서 비교하고, 조건을 만족하면 del로 잘라버리면 된다. 쓸데없이 스택 2개 만들고 쇼를 할 필요가 없다.