괄호 풀기 - Stack안쓰고 풀기

개요

코딩테스트 단골문제 괄호 푸는 문제를 Stack 을 안쓰고 풀어보겠습니다. 스택을 안써서 덜 복잡하다는 장점이 있고 덜 복잡하니 직관적이고 구현하기가 비교적 쉽다는 것입니다.

 

단점

이 알고리즘의 단점은 문자열의 길이가 늘어날 수록 속도가 많이 느려진다는 것입니다. 짧을때는 큰 차이가 없습니다.

(((((((((((((((((((....1억개 ()()()...()...1억개 이런식으로 ()가 늦게 출현한다면 O(N 제곱)이 나오는 문제가 있습니다.

 

하지만 100만 이하일때는 속도가 그렇게 엄청 느리진 않을 것입니다.

 

구현

if s[i] == '(' and s[i + 1] == ')':

원리는 위 코드입니다. s를 한칸씩 옮기면서 여는 괄호 다음에 닫는 괄호가 나오면 없애는 것입니다.

 

for i in range(len(s) - 1):

그래서 len(s) - 1까지만 반복을 합니다.

 

s = '((()))'

위와 같이 s의 길이가 6글자 인 경우 6-1인 5번만 0, 1, 2, 3, 4 까지만 반복 해야 s[i + 1]을 해도 IndexOutOfRange에러가 안나겠지요?

 

s = '((((()))))'

for i in range(len(s) - 1):
    if s[i] == '(' and s[i + 1] == ')':
	    sp = s.split('()')
        s = "".join(sp)
        break

print(s)

여는 괄호 '('와 닫는 괄호 ')'가 있으면 '()'를 기준으로 split합니다. if문을 탔으면 '('와 ')'가 연속해서 있다는 뜻이고 한개만 없애고 break를 해서 현재 for loop을 끝내줍니다.

 

이 동작을 '()'가 s에 없을동안 while로 반복 해줍니다.

def solution(s):
    while '()' in s:
        for i in range(len(s) - 1):
            if s[i] == '(' and s[i + 1] == ')':
                sp = s.split('()')
                s = "".join(sp)
                break
    return len(s) == 0

s = '((((()))()))'
print(solution(s))

((((()))()))

(((())()))

((()()))

((()))

(())

()

 

위 순서로 s에 있는 '()'가 모두 사라지고 len(s) == 0이면 True 아니면 False를 return하게 됩니다.

 

)(())

(())(

(()))

등 괄호가 안맞는다면 False가 나오게 됩니다.

 

더 간단히 줄이면

def solution(s):
    while '()' in s:
        sp = s.split('()')
        s = "".join(sp)
    return len(s) == 0

이렇게 해도 됩니다.

 

속도 테스트

from datetime import datetime

def solution(s):
    cnt = 0
    while '()' in s:
        sp = s.split('()')
        s = ''.join(sp)
        cnt += 1
    print('cnt:', cnt)
    return len(s) == 0 # _는 가독성 때문에 씁니다. 파이썬에서 인식 안합니다.

s = '(' * 5000000 + ')'*5000000
print(f'len:{len(s)} start:', datetime.now())
print('final:', solution(s))
print('finish:', datetime.now())

위로직은 위의 경우가 가장 느린 경우 입니다.

s = '(' * 5000000 + ')'*5000000

s는 총 1억개의 문자열 입니다.

한번 loop를 돌때 .split()을 한번 밖에 못하기 때문에 1억개의 쌍을 모두 지우려면 5천만번의 .split()을 해야 합니다. 그리고 .split()을 하러 찾아가기까지는 처음에는 5천만번 2번째는 49999999번 3번째는 49999998번 이렇게 해서 또 5천만번 을 연산 해야 합니다.

 

그러면 50,000,000 * 50,000,000 = 2,500,000,000,000,000

이만큼 연산을 해야 하기 때문에 노트북에서 하면 10분이 지나도 결과가 안나옵니다.

 

그래서 Stack을 써야 합니다.

 

 

end.