[프로그래머스] 올바른 괄호 (파이썬, 시간초과- 리스트 대신 디큐)

[문제]

 

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다.

예를 들어

- "()()" 또는 "(())()" 는 올바른 괄호입니다.

- ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

 

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

- 문자열 s의 길이 : 100,000 이하의 자연수

- 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

 

입출력 예

s	answer
"()()"	true
"(())()"	true
")()("	false
"(()("	false

 

 

[내 풀이]

처음 풀이는 아래와 같았다.

정확성은 만점이지만 효율성에서 0점을 받았다.

def solution(s):
    s = list(s)
    lst = []
    for _ in range(len(s)):
        if len(lst) == 0:
            if s[0] == ')':
                return False
            else:
                lst.append(s.pop(0))
        else: 
            if lst[-1] == '(' and s[0] == ')':
                s.pop(0)
                lst.pop(-1)
            elif lst[-1] == '(' and s[0] == '(':
                lst.append(s.pop(0))
            elif lst[-1] == ')' and s[0] == '(':
                return False
            elif lst[-1] == ')' and s[0] == ')':
                return False
    if len(lst) == 0:
        return True
    else:
        return False

 

 

[수정된 풀이]

앞 뒤 삭제가 많으면 리스트($O(n^2)$)보다 디큐($O(n)$)를 쓰는 게 좋다!

( $\because$ 리스트는 앞 삭제하면 하나씩 밀려서 시간복잡도 $O(n)$인데, len(s)만큼 반복되면 시간복잡도 $O(n^2)$가 됨)

from collections import deque

def solution(s):
    s = deque(s)
    lst = []
    for _ in range(len(s)):
        if len(lst) == 0:
            if s[0] == ')':
                return False
            else:
                lst.append(s.popleft())
        else: 
            if lst[-1] == '(' and s[0] == ')':
                s.popleft()
                lst.pop(-1)
            elif lst[-1] == '(' and s[0] == '(':
                lst.append(s.popleft())
            else:
                return False
    if len(lst) == 0:
        return True
    else:
        return False

 

 

[느낀점]

앞뒤로 삭제할 일 있으면 list 대신 deque 사용하자