프로그래머스 - 올바른 괄호 [스택/큐]

문제 설명:

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

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

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

---

문제 예시:

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

---

해결 코드:

def solution(s):
    start = 0
    end = 0
    
    for bracket in s:
        if bracket == "(":
            start += 1
        else:
            end += 1
        
        if start < end:
            return False
    
    if start != end:
        return False

    return True

스택과 큐를 사용하지 않고 풀었다. 구현 중심으로 풀어봤으며 스택과 큐를 적용하여 문제 해결을 바꿔보자

def solution(s):
    lst = list()
    
    for bracket in s:
        if bracket == "(":
            lst.append("(")
        else:
            try:
                lst.pop()
            except IndexError:
                return False

    return len(lst) == 0

프로그래머스에서 정답 코드를 참조하였다.

---

해설:

스택과 큐를 list의 pop기능을 활용하여 구현해보자

만약 "("이 먼저 들어오지 않으면 False를 return 해야 한다. 또한, "("이 먼저 들어오면 다음으로 ")"이 들어오길 expect 해야 한다.

따라서 if문으로 먼저 괄호를 확인한 후에 lst라는 list에 저장한다.

이후, else일 때는 문제 조건 상 반드시 ")"이다. 따라서, try except로 error를 건너뛰고 return 할 수 있도록 한다.

이때, pop을 진행해서 먼저 들어간 bracket이 있는지 ("("가 있는지) 확인한 후에 있으면 pop 없으면 False를 return할 수 있도록 한다. 마지막으로 len(lst) == 0으로 비어있는지 확인한다. 만약 0이 아니라면 한 쌍의 bracket이 아닌 값이 있다는 뜻이므로 False를 반환한다.