"일월오봉도"

(Code Kata 2-3) 괄호 유효성 검사하기

❓ 문제

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

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

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

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

s = "()"
return true

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

s = "(]"
return false

s = "([)]"
return false

s = "{[]}"
return true

🤔 접근 방식

• len(string)에 대한 반복문이 돌 때까지,
• 매칭이 되는 () {} []가 있으면 지워서
• 다 지운 상태로 빈 배열이면 True
• 비어 있지 않으면 False이다.

❗️ 답안

거의 다 맞지만, 틀린 답안

• 위의 접근 방식에서 반복문이 잘 돌아가지 않아
• (())[]같이 괄호 안의 괄호가 결국 지워지지 않아 True인데 False가 나온다.

def is_valid(string):
  while(len(string) == 0):
    string = string.replace("()", '')
    string = string.replace("[]", '') 
    string = string.replace("{}", '')
  if string == '':
    return True
  else:
    return False

 # 반례: '(())[]' -> True여야 하는데 False로 나온다

맞은 답안

• while 문이 아닌 for 문으로,
• range를 써서 인덱스 길이까지 순회한다
• 애초에 짝이 맞으면 개수가 짝수이기에 홀수이면 무조건 False로 반환
• 짝수이고 반복문을 돌려서 string의 길이가 0이면 True이다.
• replace를 돌렸는데도 매칭이 되지 않아 살아 있는 string의 길이는 0보다 크므로 이것 또한 False로 반환했다.

def is_valid(string):
  if len(string) % 2 == 0:
    for i in range(len(string)):  # len(string)이 아닌 len(string)//2도 괜찮다.
      string = string.replace("()", '')
      string = string.replace("[]", '') 
      string = string.replace("{}", '')
      if len(string) == 0:
        return True
  else:
    return False
  if len(string) > 0:
    return False

🔖 참고 자료

• (AskPython) 5 Ways to Remove a Character from String in Python
  
• (tistory, xangmin) 올바른 괄호 (연습문제, Level 2)