문제

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

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

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

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

s = "()"
return true

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

s = "(]"
return false

s = "([)]"
return false

s = "{[]}"
return true

나의 풀이

사실 이번 문제는 예전에 한번 스택을 공부할때 엄청 삽질하며 풀어봤던 유형의 문제라 이번에는 비교적 간단히 풀이를 할 수 있었습니다

• 2중 반복문으로 풀어도 되지만, 2중 반복문으로 풀이를 하게 되면 시간이 너무 걸리기 때문에 타임아웃이 날수도 있다.
• for문을 돌면서 현재값이랑 직전의 값이 완벽한 한쌍을 이루는지 확인해야 한다.
• '[()]' 문자열의 경우 안쪽의 '()' 괄호를 완벽한 한쌍으로 제거하고 나면 바깥쪽의 '[]' 괄호도 완벽한 한쌍인지 체크해야 하기 때문에 지나왔던 문자열도 다시 확인할 수 있어야 한다.
• 지나왔던 괄호, 제거해야 하는 괄호를 적절히 사용하기 위해서는 스택이 적당하다고 생각한다.
• 지나왔던건 스택 밑에 부터 차곡차곡 깔릴것이고, 최근건 가장 위에 쌓여 있을것이기에 스택의 가장 윗부분과 현재 값만을 비교하여 완벽한 한쌍이면 스택에 있는걸 제거, 아니면 스택에 담기, 그러면 순서대로 완벽한 한쌍을 자연스럽게 찾게 된다.
• 마지막으로 반복문이 다 돌고 나서, 빈스택이면 완벽한 한쌍을 모두 다 찾았다는 것이기에 True를 반환, 스택에 데이터가 남아있다면 완벽한 한쌍을 못찾은 것이 있다는 것이기에 False를 반환하면 된다.

def is_valid(string):
    list = []

    for i in string:
      if len(list) == 0:
        list.append(i)
      else:
        if list[len(list) - 1]  == '(' and i == ')':
          list.pop()
          continue;
        if list[len(list) - 1]  == '[' and i == ']':
          list.pop()
          continue;
        if list[len(list) - 1]  == '{' and i == '}':
          list.pop()
          continue;
        
        list.append(i)
    
    if len(list) > 0: return False
    else: return True


print(is_valid('{[]}'))