프로그래머스 Lv.2: 올바른 괄호 - Python 풀이

오늘의 문제

프로그래머스

 

내 풀이

def solution(s):
    answer = False # 초기값 설정
    stack = []# stack 리스트 생성
    for i in range(len(s)): # 문자열 s의 길이만큼 반복
        if not stack: # stack이 비어 있을 때
            if s[i] == ")": # 인덱스 i가 ")"면 -> 짝을 이루는 "("가 앞에 없는데 ")"가 나온다는 뜻이니까
                return answer # 올바르지 않은 괄호
            else: # 인덱스 i가 "("면
                stack.append(s[i]) # stack에 push
        else: # stack에 값이 존재할 때
            if stack[-1] != s[i]: # stack의 top과 인덱스 i의 값이 다르면
                stack.pop() # 괄호가 짝을 이루는 것이므로 stack을 pop
            else: # 값이 같으면
                stack.append(s[i]) # 인덱스 i의 값을 stack에 push
    if not stack: # s를 다 돌아본 후 stack이 비어 있다면
        answer = True # 모든 괄호가 짝을 이루었다는 것이므로 True
    return answer

 

아주 과거에 Swift로 백준에서 비슷한 문제를 풀었던 기억

뭐 이지하네요

주석을 상세하게 적어두었습니다만... 문제 풀이의 포인트를 정리해 보자면!

 

포인트 1) s를 맨 앞부터 하나씩 돌면서, stack의 top(= stack[-1])과 비교한다.

짝을 이루는 괄호라면 stack에서 top을 제거 -> pop

짝을 이루지 않는다면 (ex. "(" 다음 "("가 들어오는 경우) stack에 s[i]를 append -> push

 

포인트 2) stack이 비어 있다는 것의 의미를 알기.

stack이 비어 있는 경우는 1) for문의 가장 첫 번째 턴일 경우 또는 2) 이전의 턴에서 모두 짝을 이루었을 경우 이렇게 2가지 경우밖에 없다. 이를 이용하여 if not stack 조건일 때에 s[i]가 ")"라면, 짝을 이루는 "("가 앞에 없다는 뜻이 된다. 이때 바로 return answer를 통해 False로 for문을 종료하여 빠르게 처리할 수 있다.

 

감사합니다 행복하세요~!