프로그래머스 / 코딩 테스트 / 올바른 괄호

문제 설명

 

 

문제 해결 시도

 

반복적으로 '()' 문자열만 제거하면 사실상 ')' 혹은 ') ...' 관련 문자열 밖에 안 남을 것이다.

find 함수를 이용해 '()' 문자열이 존재하는지 파악하고 replace 함수로 반복적으로 지워주는 코드를 작성했다.

 

정확성 테스트는 모두 통과했지만 효율성 테스트는 하나도 통과하지 못했다.

 

def solve(s):
    while s.find('()') != -1:
        s=s.replace('()',"")
    return (len(s) <= 0)
    
    

def solution(s):
    answer = solve(s)
    return answer

 

문제 해결

 

어떻게 하면 문제를 더 효율적으로 풀 수 있을까 고민해봤다.

stack을 이용하면 조금 더 빠르게 문제를 풀 수 있었다.

 

문자 '('가 나오면 stack에 값을 추가해주고 문자 ')'가 나오면 stack의 값을 빼준다.

stack이 비어있을 때 값을 빼줄려고 한다면 괄호가 바르게 짝지어지지 않았다는 것이므로 False를 반환한다.

 

작업이 다 끝난 후, stack이 비어 있는지 확인한 결과를 반환한다.

 

def solve(s):
    stack = []
    for i in s:
        if i == '(':
            stack.append(i)
        elif i == ')':
            if len(stack) == 0:
                return False
            stack.pop()
            
    return len(stack) == 0
    
    

def solution(s):
    answer = solve(s)
    return answer

 

실행 속도 비교

 

정말 실행 속도가 심하게 차이가 나는지 궁금했다.

각 풀이 코드를 작성한 뒤, 차례대로 실행 시간을 측정했다.

 

import time

def func1(s):
    while s.find('()') != -1:
        s=s.replace('()',"")
    return (len(s) <= 0)

def func2(s):
    stack = []
    for i in s:
        if i == '(':
            stack.append(i)
        elif i == ')':
            if len(stack) == 0:
                return False
            stack.pop()
    return len(stack) == 0

if __name__ == '__main__':
    start  = time.time()
    test = '((((((((((((((((((((((((())))))))))))))))))))))))))))))' * 1000000 # 1000000부터 생각보다 심한 차이를 볼 수 있다.
    func1(test)
    print("func1 execute time : {0}".format(time.time() - start))

    start  = time.time()
    func2(test)
    print("func2 execute time : {0}".format(time.time() - start))

 

첫 번째 구현 방법과 두 번째 구현 방법의 실행 속도 차이는 test 하는 문자열의 길이가 커지면 커질수록

크게 차이가 났다.