[프로그래머스 2단계] 알고리즘 21. 괄호 확인하기

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 21. 괄호 확인하기

is_pair함수는 문자열 s를 매개변수로 입력받습니다. s에 괄호가 알맞게 짝지어져 있으면 True를 아니면 False를 리턴하는 함수를 완성하세요. 예를들어 s가 (hello)()면 True이고, )(이면 False입니다. s가 빈 문자열("")인 경우는 없습니다.

def is_pair(s):

# 함수를 완성하세요

return True

# 아래는 테스트로 출력해 보기 위한 코드입니다.

print( is_pair("(hello)()"))

print( is_pair(")("))

풀이 : 

이 문제의 핵심은 괄호 쌍의 확인! 이 문제는 Stack을 이용한 Infix 식을 Postfix 식으로 바꾸는 알고리즘을 차용하여 문제를 풀었다. 나의 알고리즘은 다음과 같다.

1. 먼저 문자열 중 '('와 ')'을 뽑아서 리스트로 만든다.
2. 그 후 스택을 하나 생성한다.
3. 리스트를 순회하면서 스택을 이용하여 괄호가 알맞은 쌍인지 판단한다.
1. 만약 '('이면 스택에 추가
2. 아니라면 스택에서 원소를 꺼낸다! 근데 스택이 비어있다면 괄호 쌍 실패
4. 스택에 원소가 남아있다면 실패

먼저 스택이란 '차곡 차곡 쌓여진 상자들'과 같다. 전형적인 후입선출 구조(LIFO : Last In First Out)이다. 쉽게 말해 나중에 들어간 것이 제일 처음 빠져나간다. 이 문제의 예를 들어서 설명하겠다. 먼저 '(hello)()' 이다. 알고리즘에 따르면 이렇게 된다.

1. list = '(hello)()' -> ['(', ')', '(', ')']
2. stack = []
3. 리스트 순회
1. ( -> stack 삽입
2. ) -> stack에 있던 ( 삭제
3. ( -> stack 삽입
4. ) -> stack에 있던 ( 삭제
4. stack은 그래서 남은게 없음 True

그 다음 ')(' 이다.

1. list = ')(' = [')', '(']
2. stack = []
3. 리스트 순회
1. ) -> 스택 pop 그러나 원소가 없기 때문에 False 반환

좀 이해가 되었는가? 만약 안된다면 스택을 활용한 후위 표현 계산기 알고리즘을 찾길 바란다. 아니면 후에 필자가 정리할 자료구조 파트를 보길 바란다. 그래서 이 알고리즘을 코드로 옮기면 다음과 같다.

def is_pair(s):

# 함수를 완성하세요

list = [i for i in s if (i == '(' or i == ')')] # 1. 문자열 중 '(' ,')'을 모아둔 리스트

stack = [] # 2. 이제 괄호를 체크할 스택

for i in range(0, len(list)):                   # 3. 리스트 순회

if list[i] is '(' :                         # 3-1. 요소가 '('이라면 스택 푸쉬

stack.append(list[i])

else :                                      # 3-2. 요소가 ')'이라면 스택 팝

try:

stack.pop()

except IndexError:                      # 근데 스택이 비어있다면 is_pair는 실패

return False

return len(stack) is 0                          # 스택이 비었다면 True 비지 않았다면 False

# 아래는 테스트로 출력해 보기 위한 코드입니다.

print( is_pair("(hello)()"))

print( is_pair(")("))