stack & queue(1)

스택은 모든 어플리케이션을 만들 때 사용되는 자료구조로
LIFO(후입선출), 초밥 접시를 생각해보면 먼저 먹은게(넣은게) 접시가 가장 아래에 있다.

큐는 FIFO(선입선출)
큐는 돈까스 줄 서는 거를 생각해보면 먼저 줄 선 사람이 먼저 가게에서 나가는 것이라고 생각하면 된다.

python은 stack과 Q를 제공하진 않지만 리스트가 모든 연산을 구현하지만
Q는 효율이 좋지 않으므로 deque를 활용한다.

아이디어:
1) 유효한 괄호인지 판단해라.

이 문제에서 먼저 생각해야할 부분은 stack을 리스트에서 활용할 수도 있지만
생성자를 이용하여 stack을 정확하게 설정해주고 그 함수를 호출하여 사용하는 방법을 사용하였다.

이 부분에서는 먼저 dic로 열고 닫는 부분을 key : value로 지정해준 뒤
stack을 활용하여 먼저 앞 부분들을 다 push하고 pop할 때, value 비교를 통한 유효한 괄호인지 판단하는 알고리즘이다.

"""
괄호로 된 입력값이 올바른지 판단하라.

입력 : ()[]{}

출력 : true


아이디어:
1. dic를 만들어 각 괄호에 대한 key, value를 설정한다.
2. 앞부분의 문자열을 붙여서 만들고
3. stack에 openr문자열이 들어올 시, 추가하고 그 후에
4. 닫히는 괄호가 들어온다면 가장 위에 부분이랑 자리가 같아야하므로 pop했을 때의
5. 괄호와 키 value상 같아야한다.
6. 다르거나 stack이 없는데 닫히는게 들어온다면 return False를 한다.

"""

class Solution:
    def isValid(self, s: str) -> bool:
        # dic 만들어준다
        pair = {
            '}' : '{',
            ')' : '(',
            ']' : '['
        }
        opener = "({["  ### 앞부분

        stack = []


        #전체 문자열을 하나씩 검색
        for char in s:

            #앞 부분에 있다면 stack에 넣기
            if char in opener:
                stack.append(char)

            #뒷 부분이라면
            else:

                #아무것도 없는 상태에서 뒷부분이 들어왔는지 확인
                if stack == []:
                    return False

                # 뒷부분이 들어왔다면 디렉토리에서 확인하고 맨 뒤에서 꺼내여 value와 pop이 일치하는지 확인
                # 일치하지 않다면 False 반환
                if pair[char] != stack.pop():
                    return False
        
        if stack:
            return False
            
        return True

leetcode 링크: https://leetcode.com/problems/valid-parentheses

링크:
https://github.com/leeseungsoo0701/python_alogrithm/blob/main/stack_queue/leetcode/20_valid_parentheses.py

leetcode 20