TIL59. CodeKata : 여러 괄호들 짝 맞추기 문제

ID짱재·2021년 10월 27일

CodeKata

목록 보기

6/18

🌈 여러 괄호들 짝 맞추기 문제

🤔 나의 Solution

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

✔️ s로 "()"가 주어진다면 True를 반환합니다.

✔️ s로 "()[]{}"가 주어진다면 True를 반환합니다.

✔️ s로 "(]"가 주어진다면 False를 반환합니다.

✔️ s로 "([)]"가 주어진다면 False를 반환합니다.

✔️ s로 "{[]}"가 주어진다면 True를 반환합니다.

def is_valid(string):
    bracket = {"(": ")", "{": "}", "[": "]"}
    for k,v in bracket.items(): 
      if string.count(k) != string.count(v): # 👈 count 갯수가 불일치하면 바로 False 반환
        return False
    res = []
    for i in string:
      if i in bracket:
        res.append(i)
      elif len(res) == 0 or bracket[res.pop()] != i: 
        return False  
    if len(res) == 0:
      return True      
s = "{(())[]}()"
print(is_valid(s)) # True

✔️ 괄호모양이 쌍이 일치하도록 딕셔너리로 만든 뒤, key와 value를 순회하며 string으로 주어진 요소의 갯수가 일치한지 확인한다. 쌍의 갯수가 불일치하면 순서 비교를 할 필요가 없기 때문에 False를 반환한다.

✔️ 위에서 False가 반환되지 않는다면 이제 순서를 비교해야 합니다. i값이 '(', '{', '[' 중 하나면 이를 res에 추가시킨다.

✔️ 만일 i값이 '(', '{', '[' 이 아닐 때, res값이 빈 배열이면 False를 반환한다. 여는 괄호 모양이 먼저 나타나 res에 담겨있지 않기 때문에 순서 쌍이 불일치하기 때문이다.

✔️ 또는 res에 무언가 있다면 res에서 pop한 값을 딕셔너리 key값으로 넣었을 때 나오는 value값과 현재 i와 비교한다. 불일치하다면 순서가 맞지 않은 패턴이기 때문에 False를 반환해준다.

✔️ for문이 모두 순회되었을 때, res가 빈배열이라면 모두 순서와 갯수가 일치하기 때문에 True를 반환한다.

✔️ s = "{(())[]}()" 이러한 배열이 주어졌을 때 res의 값은 어떻게 변화하는지 아래 적어보겠습니다.

index 0일 때 = 현재 i값 : { 현재 res : []
index 1일 때 = 현재 i값 : ( // 현재 res : ['{']
index 2일 때 = 현재 i값 : ( // 현재 res : ['{', '(']
index 3일 때 = 현재 i값 : ) // 현재 res : ['{', '(', '(']
index 4일 때 = 현재 i값 : ) // 현재 res : ['{', '(']
index 5일 때 = 현재 i값 : [ // 현재 res : ['{']
index 6일 때 = 현재 i값 : ] // 현재 res : ['{', '[']
index 7일 때 = 현재 i값 : } // 현재 res : ['{']
index 8일 때 = 현재 i값 : ( // 현재 res : []
index 9일 때 = 현재 i값 : ) // 현재 res : ['(']

🤔 다른 해결 방법

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