[Lv2.] 스택/큐 - 올바른 괄호

👉 사용 언어 : PYTHON3

올바른 괄호

✅ Solution

def solution(s):
    stack = []
    for i in s:
        if i == '(':
            stack.append(i)
        else:
            if len(stack) == 0 or stack[-1] == ')':
                return False
            else:
                stack.pop()
    return len(stack) == 0

 

👉 문제 설명 및 제한 사항

• 괄호가 바르게 짝지어졌다 ➡️ '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다
  • "()()" 또는 "(())()" : 올바른 괄호
  • ")()(" 또는 "(()(" : 올바르지 않은 괄호
• 매개변수 : '(' 또는 ')' 로만 이루어진 문자열 s
  • 길이 <= 100,000 자연수
• 리턴값 : true(= 올바른 괄호) / false(= 올바르지 않은 괄호)

👉 아이디어

• 스택(LIFO)를 활용하여 풀이
• 문자열 s에서 하나씩 추출하여 '('일 경우와 ')'일 경우를 나눈다.
  • 열린 괄호 : 무조건 스택에 추가
  • 닫힌 괄호
    • stack에 아무 원소도 없거나 제일 최근에 추가한 값이 닫힌 괄호일 경우 : 이미 올바르지 않은 괄호이므로 False 리턴
    • 나머지 경우(= 제일 최근에 추가한 값이 열린 괄호) : 스택에서 pop
• 리턴문에 스택의 길이가 0인지❓를 넣어서 열린 괄호가 짝이 없는 경우를 판별한다.

👉 깨달은 것 / 알게된 것

• 스택은 LIFO / 큐는 FIFO
• pop()과 append()는 맨 끝에서 추가와 삭제를 실행하므로 시간 복잡도 == O(1)