ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [파이썬, 자료구조 알고리즘] Stack
    Python 2024. 7. 12. 01:16

    Stack

     

    빨래통에 빨래감을 담은 후 꺼내려고 할 때, 가장 마지막에 담은 빨래감을 가장 먼저 꺼내게 되듯이,

    데이터를 한 곳에서만 넣고 뺄 수 있고, 마지막에 넣은 데이터를 가장 먼저 꺼낼 수 있는 Last In First Out 자료 구조.

     

    처음부터 구현을 할 수 있어야 한다고 해서 직접 해보기로.

     

    Stack에 들어가는 기본 단위를 Node이라고 한다. 이해하기 쉽게 Node를 빨래감이라고 하면,

    빨래감 노드은 두가지로 구성된다. 내가 갖고 있는 빨래감다음에 넣을 빨래감을 가리키는 역할.

    class 빨래감:
    	def __init__(self, item, next) # 갖고있는 빨래감, 다음 빨래감을 가리키는 포인터
    		self.item = item
       		self.next = next

     

     

    그 다음은 스택(빨래통)을 만들어주면 되는데, 처음에는 빨래통이 비어있을 테니까 top에 None값을 주고

    class Stack:
        def __init__(self): # 처음엔 빨래통이 비어있으니까 None
            self.top = None

     

    push : 빨래통(Stack)에 빨래 넣기 (우리가 빨래통에 빨래를 넣을 떄 당연히 맨 위에 쌓이듯이 위치는 top)

        def push(self, new_빨래): # 빨래통에 새로 넣을 new_빨래
            self.top = 빨래감(new_빨래, self.top) # 맨 위를 새로 넣어줄 빨래로 업뎃

     

    pop 빨래통에서 빨래 꺼내기

    (빨래통에서 맨 위의 빨래감을 꺼내면 당연히 통에 있던 맨 위 빨래감은 없어지고, 그 아래에 놓여있던 빨래감이 맨 위에 놓인 빨래감이 된다. 이 당연한 개념을 생각하면서 이해하면 좀 쉽다.)

    맨 위에 옷을 꺼낸 다음, 그 아래 옷을 다시 맨 위로 지정해줘야 다시 순서대로 착착 꺼낼 수 있기 때문에 self.top.next가 필요하다.

        def pop(self):# 꺼낼 때 
            if self.top is 빨래감: # 빨래통 비어있으면 
                return None # 없으니까 None 반환
            
            # 빨래통에 옷이 있으면
            빨래감 = self.top # 현재 빨래감 맨 위의 옷 확인
            self.top = self.top.next # 빨래감 맨 위의 옷 바로 아래있는 옷을 체크
            return 빨래감.item # 맨 위에 있었던 옷 꺼내

     

    is_empty 빨래통 비었는지 확인

        def is_empty(self): # 빨래통이 비었는지를 보려면
            return self.top is None # 우리가 꺼내고 빼고 할 수 있는 곳은 top 한 곳이니 top이 None인지만 보면 된다

     


     

    스택을 활용해서 유효한 괄호 문제를 풀어보면 된다.

    Q: Given a string s containing just the characters '(',  ')' , '{',  '}',  '[' and ']', determine if the input string is valid.

    An input string is valid if:
    Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type.


    Example 1:
    Input: s = "()"
    Output: true

    Example 2:
    Input: s = "()[]{}"
    Output: true

    Example3:
    Input: s = "(]"
    Output: false

     

    열린 괄호는 동일한 유형의 괄호, 올바른 순서로 닫아야 한다는 것. ( ) [ ] { } 얘네가 제대로 짝을 이루는지 확인하는 문제 .

    내일 이어서 풀어보는 걸로.. 한 문제 푸는데 넘 오래 걸려서... 진도가 안나간다ㅠㅠ

     

    근데.. 강의가 너무 나긋나긋해서일까... 수면유도 asmr 같다ㅠㅠㅠ 안그래도 어려운데 큰일이다ㅠㅠ 

Designed by Tistory.