[항해99] Stack

Stack

한쪽으로만 넣고 뺄 수 있는 자료구조.

 

 

회식을 예시를 들어보겠습니다.

 

보통 자리가 많은 회식 테이블은 가생이에 있기 마련입니다.

 

인원이 앉을 때 순서대로 들어간다면 F - E - D - C - B - A 순으로 들어가서 앉겠죠.

회식이 무르익습니다. 

아아... 신입사원 김씨는 F자리에 앉았는데 눈이 캄캄해집니다.. 나가기에 공간이 충분하지 않은거죠...

화장실을 가기 위해 앉은 자리에서 모든 자리 사람들을 일으켜서 밖으로 내보냅니다. 화장실을 가야죠. 

 

모든 직원이 다 자리에서 나오고 나서야, 김씨는 화장실을 갈 수 있었습니다.

 

화장실을 다녀온 김씨는 아뿔싸! 하고 말았습니다.

왜일까요?~~

다시 김씨가 제일 안쪽 자리에 앉으려면 다시 모든 직원이 나와야 하거든요..

 

다소 썰렁한 개그였지만 머릿속에 꼭 남아서 술자리에서 안쪽 사람이 나간다고 비켜달라하시면 

"아아... 스택형으로 앉아서 그렇구나.." 라고 중얼거리면서 쿡쿡.. 웃어주시면 다들 좋아하실거라 믿습니다. 

 

스택의 구조

class Node:
    def __init__(self, item, next):
        self.item = item
        self.next = next


class Stack:
    def __init__(self):
        self.top = None

    def push(self, value):
        self.top = Node(value, self.top)

    def pop(self):
        if self.top is None:
            return None

        node = self.top
        self.top = self.top.next

        return node.item

    def is_empty(self):
        return self.top is None

 

스택은 한쪽으로만 자료가 들어가고 나가기 때문에, LIFO (Last In First Out) 라고 부릅니다 

pop은 스택에서 젤 위에 있는 노드를 빼주는 함수, 

push는 스택에 제일 위에 노드를 넣는 함수 입니다.

BOJ - 괄호

https://www.acmicpc.net/problem/9012

9012번: 괄호

T = int(input())
for _ in range(T):
    expr = input()
    S = []
    flag = "YES"
    for i in (expr):
        if i == "(":
            S.append(i)
        elif i == ")":
            if len(S) == 0:
                flag = "NO"
                break
            else:
                t = S.pop()
                if t != "(":
                    flag = "NO"
                    break
                
    if len(S) != 0:
        flag = "NO"
    print(flag)

다음 나올 괄호문제보다 쪼금 쉬운 버전입니다.

괄호의 종류가 하나라서 스택에 ( 면 넣고 ) 면 빼는!

False조건은 1. 스택이 비었을 때 )가 나온다면, 2. 문자열이 끝났는데 스택은 아직 차있다면 ["(" 괄호가 남은거겠죠? ]

유효한 괄호

https://leetcode.com/problems/valid-parentheses/description/

Valid Parentheses - LeetCode

def is_valid_parenthesis(s):
    pair = {
        "}": "{",
        ")": "(",
        "]": "[",
    }
    opener = "({["
    stack = []
    for char in s:
        if char in opener:
            stack.append(char)
        else:
            if not stack:
                return False
            top = stack.pop()
            if pair[char] != top:
                return False

    return not stack # 비었으면 True

 

스택을 이용하는 유명한 문제입니다. 

 

만약 여는 괄호라면 스택에 넣은 뒤, 닫는 괄호일 때 스택의 제일 위 원소( pop의 결과)와 다르다면, 혹은 비었다면, 혹은 모든 괄호를 처리했는데 스택에 원소가 남았다면 ( 여는 괄호가 남은거겠죠 ) False를 리턴하고, 끝까지 확인했을 때 모든 괄호가 잘 닫혔으면 (스택은 비었겠죠 ) True를 리턴하는 간단한 방식입니다. 

중복문자 제거

https://leetcode.com/problems/remove-duplicate-letters/

Remove Duplicate Letters - LeetCode

import collections


class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        counter, stack = collections.Counter(s), []
        for char in s:
            counter[char] -= 1
            if char in stack:
                continue
            while stack and char < stack[-1] and counter[stack[-1]] > 0:
                stack.pop()
            # stack : stack이 비어있으면 바로 붙여! 
            # char < stack[-1] : 스택 마지막원소보다 현재 문자가 크면 바로 붙여!
            # counter[stack[-1]] : 스택의 마지막 원소가 0개면 바로 붙여!
                # ba 라면 [b] 상태에서 counter[b] = 0이니까 뒤에 b가 못 오니까 걍 붙여란 말
            # 만약 이 조건을 만족 못하면 만족 할 때까지 스택에서 빼내
            stack.append(char)
        return "".join(stack)

 

꽤나 어려운 문제였습니다. 

문제에서 나온 lexicographical이라는 말이 "사전식"이라는 말인데, 일단 중복 문자를 "제거"할 뿐, 재배치하지 않는다는게 핵심입니다.

그 말은 e b e 라는 문자를 중복을 제거한다면 eb 와 be 두가지 형태가 있을텐데, 이 형태중 be가 사전에 먼저 나오는 글자기 때문에 be를 채택한다! 라는 말입니다.

 스택을 이용한다는 생각을 스택에서 보지 못한다면 하기 힘들었을 수도 있겠네요. 

스택수열

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

아직 풀고있습니다.. 생각이 더 필요할 것 같네요. 풀게되면 가져오겠습니다.