[백준] 9935번: 문자열 폭발

이미지 출처 : https://velog.io/@ddosang/Algorithm-%EB%B0%B1%EC%A4%80-9935

 

11회만에 맞춘 정답

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

9935번: 문자열 폭발

Solution

시간복잡도 : O(n+m)

a = input().rstrip()
b = input().rstrip()

stack = []

blen = len(b)

for char in a:
    stack.append(char)
    if len(stack) >= blen:
        if ''.join(stack[-blen:]) == b:
            del stack[-blen:]

if not stack:
    print('FRULA')
else:
    print(''.join(stack))

스택에 관해 물어보는 문제였다.

알고리즘 자체는 그렇게 어려운 문제는 아니었지만 100만자 이하의 시간 복잡도를 2초 이내로 해결하기 위해선 효율성을 좋게만들 필요가 있었다.

본인이 짠 코드와 다르게 gpt에게 시간복잡도에 대해 물으니 굉장히 간결한데 join 함수에 관해 새롭게 알게 되었다.

join함수에 관하여

list(문자열) ↔ ''.join(list)

문자열.join(리스트)

# 공백 없이 문자열 합치기
print("".join(["a", "b", "c"]))  # 'abc'

# 공백으로 문자열 합치기
print(" ".join(["a", "b", "c"]))  # 'a b c'

# 쉼표와 공백으로 문자열 합치기
print(", ".join(["a", "b", "c"]))  # 'a, b, c'

attempt

시간복잡도 : O((n-m+1)* m)

• 원래 첫 번째 문자열 a를 순회하면서, 매번 두 번째 문자열 b와의 일치를 확인했다. 이 과정에서 일치하지 않는다면, b 문자열을 다시 복사하고, 인덱스를 조정하는 작업을 하므로 시간 복잡도가 오래걸린듯.

import sys

a = sys.stdin.readline().rstrip()
b = sys.stdin.readline().rstrip()
alst = []
blst = []
rawlst = []
alst = list(a)

# print(alst)

rawlst = list(b)
blst = list(b)

blst.reverse()
rawlst.reverse()
# print(blst)
# print(rawlst)

breaker = False

i=0
while True:
    if breaker:
        break

    while True :
        if i == len(alst) or alst == []:
            breaker = True
            break

        # print('blst[-1] : ', blst[-1], 'alst[i] : ', alst[i], 'i :', i, 'blst : ', blst)
        if blst[-1] == alst[i]:
            blst.pop()
            # print('blst.pop()')

            if blst == []:
                blst = rawlst.copy()

                alst = alst[:i-len(rawlst)+1] + alst[i+1:]
                # print(alst)
                i = i-len(rawlst)+1-1
                break 
        else:
            if blst == rawlst:
                blst = rawlst.copy()
            else:
                # print('here')
                blst = rawlst.copy()
                i -= 1

        i+=1

if alst == []:
    print('FRULA')
else:
    for i in alst:     
        print(i, end="")

 

다음에 이 문제를 다시 만나면..

필자는 a, b를 각각 input으로 받을 때 b라는 리스트 자체를 하나의 스택으로 생각하고, 스택이 터질 때마다 rawlst로 초기화되는 알고리즘을 짰다. 하지만 시간 복잡도로 봤을 때 ** 하나의 새로운 스택 **을 새로 만들고 그 스택에 정답을 담는 알고리즘은 생각하지 못했다. 다음부턴 문자열을 리스트로 한번에 바꿔주는 list함수와 ''.join함수, 그리고 스택을 새로 파는 알고리즘까지 배운 것을 잘 활용해서 문제를 풀어봐야 할 것 같다.