code-taka 07(is_valid)

nichol·2022년 5월 21일
0

Algorithm & DataStructure

목록 보기
7/12

문제

s는 여러 괄호들로 이루어진 String 인자입니다. s가 유효한 표현인지 아닌지 true/false로 반환해주세요.
종류는 '(', ')', '[', ']', '{', '}' 으로 총 6개 있습니다. 아래의 경우 유효합니다.
한 번 괄호를 시작했으면, 같은 괄호로 끝내야 한다. 괄호 순서가 맞아야 한다.

풀이

stack 과 queue의 개념

  1. stack : 리스트에서 가장 마지막에 들어간것이 가장 먼저나온다.
  2. queue : 리스트에서 가장 먼저 들어간것이 가장 먼저 나온다.

이번문제는 stack의 기본 개념의 예제와 같은 문제이다.

풀이의 대전제

  1. 짝수는 무조건 False
  2. 닫는 괄호가 먼저있으면 False
  3. 여는 괄호와 바로 다음 괄호가 닫는괄호일 경우, 그 괄호와 대응하는 닫는괄호가 아닐경우는 무조건 False
  4. 여는 괄호 바로 다음괄호가 대응하는 괄호일경우 지우고를 반복하여 반복이 끝날때 남은괄호의 총길이가 0 일경우만 True
def is_valid(string):
    a = {'}':'{', ']':'[', ')':'('}   # 중요점 1
    
    if len(string)%2 == 1:
      return False
    else:
      l1=[]
      for s in string:
        if s in a.keys():             # 중요점 2
          if l1:
            p=l1.pop() 				  # 중요점 3
            if not a[s] == p:
              return False
          else:
            return False  
        else:
          l1.append(s)
      return len(l1)  == 0

중요점 1/2

  • 딕셔너리를 만들때 대전제 2번을 위해 key값은 여는 괄호 valua값은 닫는 괄호로하여 조건문에 활용할 수 있도로록 만든다.

중요점 3

  • pop함수
    pop함수는 변수지정없이 l1.pop()하면 가장 마지막 리스트 인자를 삭제하지만 변수를 지정한다면 그 삭제된 인자가 변수에 담긴다.
profile
WEB Developer

0개의 댓글