[Leetcode] 20. Valid Parentheses

✅ 문제 - 유효한 괄호

 

 

 

이 문제는 s의 괄호 짝이 맞는 경우 true, 맞지 않는 경우 false 반환하는 문제이다.

 

---

 

✅ 풀이 코드

이 문제는 전형적인 스택 구조이다. 

예를 들어,

s가 {[]} 라면 [ 가 나중에 들어갔기 때문에 ] 가 먼저 나와야하고, 그다음에 처음 들어간 { 에 맞는 } 가 나와야 한다.  

 

방법1) 

class Solution:
    def isValid(self, s: str) -> bool:

    # 괄호 짝 dict로 만들기(key-value)
        pair = {
            ')' : '(',
            '}' : '{',
            ']' : '[',
        }
		
        #opener를 담을 리스트
        stack = [] 
        opener = "({["

        for item in s:
            # opener는 stack에 넣기
            if item in opener:
                stack.append(item)

            # opener가 아닌 경우
            else:   
                # stack이 비어있으면(맞는 짝이 없다는 이야기)
                if not stack: 
                    return False

                # stack이 비어있지 않으면 가장 뒤에 있는 opener 꺼내서
                top = stack.pop()
                # 방금 꺼낸 것과 짝이 맞는지 확인 후 다를 경우 false
                if pair[item] != top:
                    return False

        return not stack

💡Point
1. 괄호 짝을 key-value에 맞춰 딕셔너리 방식으로 만든다.
2. s를 순회하며 오프너들만 stack이라는 빈 리스트에 담는다.
3. 비교하려는 괄호가 opener가 아닐 경우 
 3-1) stack이 비어있으면 맞는 짝이 없으므로 false
 3-2) stack이 비어있지 않으면 stack에 마지막으로 들어간 opener를 꺼내 pair의 value값과 일치여부 확인
4. s 순회 후 stack 리스트가 비어지게 되면 opener가 맞는 짝을 다 찾아갔기 때문에 true 반환

 

 

---

 

방법2)

def valid(s: str) -> bool:
    pair = {
        ')': '(',
        '}': '{',
        ']': '['
    }

    stack = []

    for item in s:
        if item not in pair:
            stack.append(char)
            
        elif not stack or table[char] != stack.pop(): 
            return False

    return len(stack) == 0

💡Point
1. 괄호 짝을 key-value에 맞춰 딕셔너리 방식으로 만든다.
2. s를 순회하며 pair에 key값으로 존재하지 않을 경우 stack이라는 빈 리스트에 담는다.
   → 결론적으로 value인 여는 괄호들만 stack에 담기게 되므로, 풀이1에서 opener를 지정해준 것과 같은 효과임
3. elif에 따라 여는 괄호가 아닐 경우,
 3-1) stack이 비어있으면 맞는 짝이 없으므로 false
 3-2) stack이 비어있지 않으면 stack에 마지막으로 들어간 opener를 꺼내 pair의 value값과 일치여부 확인
4. s 순회 후 stack 리스트가 비어지게 되면 opener가 맞는 짝을 다 찾아갔기 때문에 true 반환