21.3.10

알고리즘 7일차

문제 : 세 가지 괄호 스트링이 유효한 표현인지 판별하기

주요 개념 : 스택(Stack)

1. stack이란?

• 후입선출. 즉 나중에 들어온 것을 먼저 꺼내는 방식
• 반대 개념 : 큐(선입선출)
• push & pop
• 알고리즘 활용 예제 : 괄호 열고 닫기

참고 블로그

2. stack 클래스 구현
   

• 여는 괄호는 push, 닫는 괄호는 pop으로 꺼내어(삭제과정. 근데 끝값부터) 서로 맞춰보기

  pop? : 리스트의 주어진 위치에 있는 항목 삭제하고 그 항목을 돌려줌(뭐 삭제 했는지 보여줌) 보통 인덱스를 지정하지 않으면 마지막 항목을 삭제한다.

3. 원리 : 임의의 스택 리스트를 주고 값이 없으면 그 값을 추가해주는데 조건에 맞지 않는 모든 항목에 대해서 False를 줌.(조건에 맞게 append도 안 되었고 스택에 맞게 지워지지도 않는 값.). 마지막에 리턴값이 0이 되는걸 보여주는 것은 pop으로 모두 지워졌기 때문.

코드

def is_valid(string):
  stack = []
  group = {
    ')' : '(',
    ']' : '[',
    '}' : '{'
  }

  for i in string:
    if i not in group:
      stack.append(i)
    elif not stack or group[i] != stack.pop():
      return False

  return len(stack) == 0


print(is_valid("(())[]"))

1. 코드 예시 :

• 기본적인 (), ()(), '[]', {} 등은 모두 패스
• (()) 등이 허용되는 이유 : 딕셔너리 & 스택

  (, (는 일단 값이 비어있기 때문에 넣고 ), )는 팝 되는 값이 나중에 들어온 값과 딕셔너리 순서와 같으므로)

• ({)이 안 되는 이유도 위의 조건에서 걸리므로 False( '(', '{'까진 가지만 )가 }가 pop되는 순간과 다르기 때문에.

  예 : (]의 경우 먼저 값이 없을 때 ( 넣고 다음에 ]가 들어오는데 이 때 팝되는 ]값과 (의 짝인 )가 같지 않기 때문에 에러가 난다.

• 그 외 ]], 등도 모두 같음

2. 잘 몰랐던 개념 :

• 스택
• pop

3. 그 외 시도한 점 :

• 모든 경우에 대해 인덱싱
• for 반복문 통한 값 직접 집어넣기
• 스택 사용하긴 했으나 정확한 뜻 모르고 사용