CodeKata - 괄호 찾기(stack)

이번 코드카타는 시간 안에 풀지 못해 모범 답안을 해석하며 stack의 개념에 대해 공부 했고, 마침 오후 세션 이었던 stack & queue을 듣고 다시 한번 stack을 공부 할 수 있는 기회 였다.

문제

s는 여러 괄호들로 이루어진 String 인자입니다.
s가 유효한 표현인지 아닌지 true/false로 반환해주세요.

종류는 '(', ')', '[', ']', '{', '}' 으로 총 6개 있습니다. 아래의 경우 유효합니다.

• 한 번 괄호를 시작했으면, 같은 괄호로 끝내야 한다.
• 괄호 순서가 맞아야 한다.

내 생각

1. 일단 홀수면 짝을 이룰 수 없으니까 False
2. 괄호의 시작이 무조건 왼쪽 괄호여야 되므로 그렇지 않으면 False
3. 괄호의 시작이 왼쪽 괄호면 그에 대응하는 오른쪽 괄호 찾기 시작하고 없으면 False
4. 대응하는 괄호가 있으고, 그 안에 다른 괄호들이 있으면 위의 과정을 반복
5. 4.에서 찾은 대응하는 오른쪽 괄호 다음 괄호부터 위의 과정을 다시 반복

모범답안

def is_valid(string):
	left = ['(', '{', '[']
	right = [')', '}', ']']
	stack = [ ]
    
	for letter in string:
		if letter in left:
			stack.append(letter)
		elif letter in right:
			if len(stack) <= 0:
				return False
			if left.index(stack.pop()) != right.index(letter):
				return False
	return len(stack) == 0

1. 검사할 괄호들을 stack에 차례로 쌓는다.
2. 왼쪽 괄호이면 아무 조건 없이 stack에 쌓는다.
3. 오른쪽 괄호이면 stack이 비였는지 확인하고 비였으면 False
   => 오른쪽 괄호부터 시작하는 경우
4. stack이 비여있지 않으면, stack에서 값을 꺼내오고, 현재 오른쪽 괄호랑 비교하여 대응하는 괄호인지 판단.
5. 만약 모든 괄호들이 대응하면 stack은 빈 리스트가 되어 True을 반환