[Python] 프로그래머스 / 스택/큐 / 올바른 괄호 / pop() / stack

def solution(s):
    if s[0]==")" or s[-1]=="(":
        return False
    
    while s and s[0]=="(" and s[-1]==")":
        for i in range(len(s)):
            if s[i:i+2]=="()":            
                s = s.replace("()", '')
        return True  #)()) 인데 True 발생
    return True

 

 

replace() 함수는 문자열을 전체적으로 탐색하여 해당 부분을 찾아 치환하기 때문에 매우 비효율적.

특히 반복문 안에서 replace() 함수를 사용하는 것은 반복할 때마다 전체 문자열을 다시 탐색하여 교체하기 때문에 성능이 매우 떨어지게 된다.

 

def solution(s):
    stack = []
    # stack에 '('을 넣어 s의 ')'과 짝을 짓는다.
    for i in s:
        if i=='(':
            stack.append(i) # '(' 일 경우 stack에 저장
        else:
            # stack에서 가장 마지막에 추가된 '('과 ')'
            if not stack: # stack이 비었으면
                return False
            stack.pop() # 가장 마지막에 넣은 '('을 제거해 ')'과 짝을 지어줌
    if len(stack)==0:
        return True
    return False # 반복문을 돌고도 원소가 남으면 false