[코딩인터뷰] 스택 - 유효한 괄호 문제풀이

문제

괄호로 된 입력 값이 올바른지 판별하라

 

입력: ()[]{}
출력: true

 

 

나의 코드

문제 : leetcode.com/problems/valid-parentheses/

# 괄호로 된 입력 값이 올바른지 판별하라

# 입력 ()[]{}
# 출력 true

# 리스트로 구현해보자.

class Solution:
    def isValid(self, s: str) -> bool:
        dict = {"(": ")", "[": "]", "{": "}"}

        # 문자열을 리스트로 변환
        value_list = list(s)
        print(value_list)

        i = 0

        while i < len(value_list):
            key = value_list[i]

            # 존재한다면
            if dict.get(key) in value_list:
                value_list.remove(dict[key])
            else:
                return False

            i = value_list.index(key) + 1

        return True


f = Solution()
print(Solution.isValid(f, "([)]"))

 

나는 문자열 s를 리스트로 변환하였고, 괄호를 쌍으로 key, value로 딕셔너리에 저장했다. 반복문을 돌려서 i번째의 value가 해당 리스트 안에 존재하지 않는다면 False를 리턴한다. 만약 존재한다면 해당 값을 리스트에서 삭제하고 그 다음 i로 넘어간다. 그 다음 i는 현재 i번째의 다음 인덱스로 지정해준다. i = i + 1이 아닌 이유는 리스트의 remove 함수 후에는 인덱스가 변경되기 때문이다.

 

해당 코드로는 테스트 몇개의 코드가 fail이 된다. 그 중 하나의 경우가 s = "([)]" 이 경우인데 내 코드는 괄호를 여는 괄호, 닫는 괄호가 쌍이 된다면 True이기 때문에 Flase가 출력되어야하는 해당 경우에는 실패하게된다. 또한 스택을 활용했다고 볼 수 없다. 

 

 

 

 

정답코드

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        table = {
            ')': '(',
            '}': '{',
            ']': '[',
        }

        # 스택 이용 예외 처리 및 일치 여부 판별
        for char in s:
            if char not in table:
                stack.append(char)
            elif not stack or table[char] != stack.pop():
                return False
        return len(stack) == 0

출처 : github.com/onlybooks/algorithm-interview/blob/master/3-linear-data-structures

 

 

 

 

 

문제풀이

(1) 설명

table = {
            ')': '(',
            '}': '{',
            ']': '[',
        }

 

딕셔너리 table 변수를 생성한다.

 

 

(2) 설명

if char not in table:
	stack.append(char)

 

반복문이 실행되면서 table 안에 존재하는지 체크한다. key는 ')', '}', '] 모두 닫는 괄호이다. 만약 여는 괄호의 차례일 경우에는 stack에 push한다.

 

 

(3) 설명

elif not stack or table[char] != stack.pop():
	return False

 

그리고 stack이 비어있지않거나 table[char] 이 stack.pop()과 일치하지 않으면 그대로 False를 리턴한다. 이 elif문의 의미를 알아보자. 우리는 위 if문에서 여는 괄호의 차례일때 stack에 해당 괄호를 넣었다. 그리고 elif문에서는 char이 닫는 괄호일때 타게되는데, 여기서 table[char]을 하면 닫는 괄호에 대한 여는 괄호 값이고, 해당 여는 괄호값은 아까 if문에서 넣은 stack 안에 있을 것이다. stack은 후입선출 이므로 마지막에 넣은 괄호와 현재 차례인 닫는 괄호에 대한 여는 괄호가 같지 않다면 False를 리턴한다. 또한 stack이 비어있지 않을 경우에도 괄호의 짝이 맞지 않는다는 뜻이므로 False를 리턴한다.