(Python) 알고리즘 문제 D+8

문제

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

종류는 '(', ')', '[', ']', '{', '}' 으로 총 6개 있습니다.
아래의 경우 유효합니다.
한 번 괄호를 시작했으면, 같은 괄호로 끝내야 한다.
괄호 순서가 맞아야 한다.

예를 들어 아래와 같습니다.

s = "()"
return true

s = "()[]{}"
return true

s = "(]"
return false

---

해답 (my solution)

def is_valid(string):
  stack= []
  dict = {"(": ")", "{": "}", "[": "]"}
  if len(string) == 1:
    return False
  
  for i in string:
    if i in dict:
      stack.append(i)     
    elif len(stack) == 0 or dict[stack.pop()] != i: 
      return False
  return len(stack) == 0 

• stack 의 LIFO 특징을 이용해서 문제를 해결 할 수 있다.
• 먼저 빈 리스트stack을 생성한다. 여기에 for문으로 체크한 string의 요소가 들어 갈 것이다.
• 딕셔너리dict에 괄호를 종류별로 저장한다. 이 때, key에는 열림괄호, value에는 닫힘괄호를 저장한다.
• string의 길이가 1 일때는 False를 리턴한다.
• for문에서 string의 각각의 요소를 확인한다.
  • 요소가 dict에 있는지를 확인한다 (딕셔너리이므로 key값에 있는지가 확인된다.)
  • 존재할 경우, stack에 해당 요소를 더해준다.
  • 존재하지 않을 경우(닫힘괄호), stack의 길이가 0이거나, stack에 들어가 있는 요소의 value값으로 존재 하지 않는 경우, False를 리턴한다.
    • stack.pop은 마지막 요소를 지우고 불러온다. 따라서 dict[stack.pop()]은, 현재 요소가 stack에 저장된 열림괄호에 해당하는 value인지를 체크한다.
    • stack의 길이가 0인지 확인을 조건에 넣은 이유는, 닫힘괄호로 시작하는 경우를 확인하기 위해서이다.
  • for문이 다 돌고 난 후, 유효한 string이라면 길이가 0이어야 한다. 따라서, True를 리턴하고 계산을 마친다.
    • 닫힘괄호가 등장했을 때, elif문의 stack.pop이 실행되어, stack에서 요소가 제거되기 때문에, 최종 string의 길이는 0이어여만 유효하다.

---

해답 (model solution)

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