[프로그래머스|Python] 올바른 괄호

✔️ 문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12909

문 제

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

---

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

---

제한사항
문자열 s의 길이 : 100,000 이하의 자연수
문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

해 설

def solution(s):
    stack = []
    
    for char in s:
        if char == '(':
            stack.append(char)  # 여는 괄호를 스택에 추가
        elif char == ')':
            if not stack:  # 스택이 비어있다면 짝이 맞지 않음
                return False
            stack.pop()  # 닫는 괄호에 대해 스택에서 여는 괄호 제거
    
    # 모든 괄호가 짝지어졌는지 확인
    return len(stack) == 0

다시 풀었는데 이번에는 기존 코드에서 elif 문 안의 stack.pop()을 stack.pop(0)이라고 했댜
그런데 시간초과가 떴다!
stack.pop()의 경우 시간복잡도가 O(1)이지만, stack.pop(0)의 경우에는 O(n)이 된다. 왜냐하면 첫번째 요소를 제거한 후 리스트의 나머지 요소들을 모두 왼쪽으로 한 칸씩 이동시켜야하기 때문

그렇군..