[Programmers] L2. 올바른 괄호 (스택/큐/Python)

---

[문제 링크] 👇

프로그래머스

---

풀이 방법

1️⃣ ")" 를 만날 때 까지 "(" 를 큐에 넣는다.

queue.append(n)

 

2️⃣ ")" 를 만나면 큐의 맨 뒤에서부터 "(" 를 꺼낸다.

• 단, "(" 를 꺼내기 전에 큐가 비어있지 않은지 확인한다. 큐가 비어있으면 꺼내려고 할 때 에러가 난다.
• 큐가 비어있지 않으면 꺼내고 비어있으면 반복문을 중단시킨다.
  • 처음부터 ")" 를 만나면 문자열을 끝까지 확인해도 올바르게 짝지어지지 않기 때문이다. 

queue.pop()

 

3️⃣ 큐가 비어있지 않으면 False를 반환하고, 비어있으면 True를 반환한다.

 

 

★ True 예시

큐가 비어있으므로 True 를 반환한다.

 

 

★ False 예시

큐가 비어있지 않으므로 False 를 반환한다.

 

Solution

from collections import deque

def solution(s):
    answer = True
    queue = deque()  # 비어있는 큐 생성
    for i in s:
        if i == "(":
            queue.append(i)  # 뒤에서부터 넣기
        else:
            if len(queue) != 0:  # 큐가 비어있지 않으면
                queue.pop()  # 맨 뒤에서부터 꺼내기
            else:  # 큐가 비어있으면
                queue.append(i)
                break

    if len(queue) > 0:  # 큐가 비어있지 않으면 올바르게 짝지어지지 않았다는 것
        answer = False

    return answer

 

 

개선할 점

• 이 코드에서 큐(deque)를 사용해 괄호가 올바르게 짝지어졌는지 확인하는 방식은 잘 작동하지만, 큐 대신 list를 사용하는 편이 간단하다.
• deque의 장점인 양방향 추가/삭제가 필요하지 않으므로, list로도 충분히 처리할 수 있다.
• 또한, 코드에서 answer 변수를 미리 True로 정의하는 대신, 마지막에 조건을 직접 반환하면 코드가 더 간결해진다.
• 이렇게 개선하면 길이가 100,000까지 되는 s 문자열도 효율적으로 처리할 수 있다.

 

개선된 코드

def solution(s):
    stack = []
    for char in s:
        if char == "(":
            stack.append(char)  # 열린 괄호는 스택에 추가
        else:
            if stack:  # 스택이 비어있지 않으면
                stack.pop()  # 스택에서 열린 괄호 하나 제거
            else:
                return False  # 닫힌 괄호가 더 많아지는 경우 False 반환

    return len(stack) == 0  # 스택이 비어있어야 올바른 괄호

 

---