Python: Code Taka 2주차 3

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

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

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

s = "()"
return true

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

s = "(]"
return false

s = "([)]"
return false

s = "{[]}"
return true

나의 답

def is_valid(string):
  if not string or len(string) == 1:
    return False
  
  a_dic = {"(": 1, "[": 1, "{": 1, ")": 0, "]": 0, "}": 0}
  b_dic = {")": "(", "}": "{", "]": "["}
  temp = []
  
  for index in range(len(string)):
    if index == 0 and a_dic[string[index]] == 0:
      return False
    
    if a_dic[string[index]] != 0:
      temp.append(string[index])
    else:
      if temp[-1] != b_dic[string[index]]:
        return False
      else:
        temp.pop()
  
  return True

1. 괄호가 열리고 닫힐 때를 판단할 수 있는 딕셔너리를 만든다.
2. 열리는 괄호에 매칭되는 닫히는 괄호의 키, 값 쌍의 딕셔너리를 만든다.
3. 특정 괄호가 열렸을 때 배열 temp 에 해당 괄호를 저장한다.
4. 특정 괄호가 닫혔을 때, temp 의 가장 마지막 값이 열리는 괄호라면 temp 의 마지막 값을 pop() 메서드를 사용하여 제거한다.
5. 4번에서 괄호가 닫혔을 때 temp 의 가장 마지막 값과 다르다면 그 시점에서 False 를 리턴한다.
6. 마지막까지 다 검사하여 False 가 리턴되지 않았을 때 True 가 반환되어 유효한 괄호의 배열이라고 판단할 수 있다.

느낀점

이 문제는 뭔가 풀릴 듯 말듯 하여 1시간 30분을 잡고 있었던 문제이다.
괄호가 닫혔을 때 해당 괄호의 쌍을 찾기 위하여 아래와 같은 딕셔너리를 만든 것이 좋았던 것 같다.

  b_dic = {")": "(", "}": "{", "]": "["}

하지만, 효율적인 코드라고 느껴지지 않았다.

솔루션

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

1. 내가 작성했던 답과 비교했을 때 괄호가 열리고 닫히는 판단을 좀 더 스마트하게 해놓았다.
2. 따라서 좀 더 가독성 좋은 코드가 되었고, 변수 이름도 명확하다. left 배열은 열리는 값, right 배열은 닫히는 값.
3. 열리고 닫히는 값을 체크하기 위한 코드도 훨씬 간편하다.
4. stack 을 이용하였다.