12/14 올바른 괄호

https://school.programmers.co.kr/learn/courses/30/lessons/12909

.

스택과 관련된 대표적인 예제인 올바른 괄호 쌍 판별하기 문제이다.

나는 보편적인 방법인 스택을 이용해서 풀었다.

내 풀이

def solution(parenthesis):
    stack = []
    answer = True
    for p in parenthesis :
        if p == '(' :
            stack.append(p)
        else :
            if len(stack) != 0 and stack[-1] == '(':
                stack.pop()
            else :
                answer = False
                break
                
    if len(stack) != 0 :
        answer = False
        
    return answer

try ~ except문을 활용한 풀이이다. 이 구문에서는 리스트가 비어있는 경우 pop()을 실행하면 IndexError가 일어남을 이용한 예외처리이다.

괄호 검사의 의사코드를 간단하게 작성하면 다음과 같다.

• ’)’을 만났을 때

  • stack의 top이 ‘(‘ => True

  • stack의 top이 ‘)’ => False

  • stack이 비어있는 경우 => False

세가지 경우 중 두번째는 ‘)’이 끝까지 없어지지 않으므로 마지막 return len(st) == 0으로 커버가 된다.

세번째는 stack이 비어있으므로 예외처리 코드에서 IndexError로 커버가 되므로 모든 경우에서 괄호 검사가 가능하게 된다.

다른 사람의 풀이 1

def solution(parenthesis) :
    st = list()
    for p in parenthesis :
        if p == '(' :
            st.append(p)
            
		if p == ')' :
            try :
                st.pop()
            except IndexError :
                return False
            
	return len(st) == 0

다른 사람의 풀이 2

def solution(parenthesis) :
    pair = 0
    for p in parenthesis :
        if p == '(' : 
            pair += 1
        elif p == ')' :
            pair -= 1
		
        if pair < 0 :
            return False
        
	return pair == 0

처음에 이 풀이를 언뜻 보고 닫는 괄호의 개수와 여는 괄호의 개수는 같지만 순서가 다를 때도 통과하는 것 아닌가 하는 생각이 들었다. 하지만 이 풀이에서 pair 변수를 이용하는건 stack의 개념과 크게 다르지 않다. 여는 괄호가 나온 개수만큼 닫는 괄호의 개수도 나와야 pair가 0이 되지 않고 닫는 괄호의 개수가 많아지는 순간 pair가 음수가 돼서 if pair < 0 : 구문에서 필터링이 되기 때문이다.