스택 (Stack) 자료구조 : Python 개념 설명 + LeetCode (Stack 문제들)

2025년 새해가 밝았습니다!

 

올해는 청뱀을 상징한다고 하네요.

동양 문화에 의하면 청색은 나무를 상징하고, 이는 곧 생명력과 성장이라는 의미를 내포한다고 합니다.

또한 뱀은 유연함과 지혜를 뜻한다고 합니다.

 

저 역시 지혜롭고 유연한 태도로 2025년에도 열심히 성장해야겠다는 다짐을 하게 되네요 ^_^

빠르게 변하는 세상을 피할 수 없다면 즐겨보겠다는 마인드로 임해볼게요!

 

---

 

# 스택(Stack) 개념 설명

스택은 LIFO(Last In, First Out) 작업을 위해 사용되는 자료구조입니다.

차곡차곡 쌓은 타월 및 접시 등을 떠올리면 스택 구조를 이해하는데 큰 도움이 됩니다!

 

스택의 역사를 짚어서 거슬러 올라가다 보면, 네임드 컴퓨터 공학자인 '앨런 튜링(Alan Turing)'을 마주하게 됩니다.

앨런 튜링은 서브루틴(전체 작업을 부분적으로 구성하는 함수들) 호출 과정을 bury, 되돌아오는 과정을 unbury라고 칭했다고 하네요.

이것이 스택 자료구조의 기원이라고 합니다!

 

그리고 디버깅 시에 꼭 보게 되는 에러 내용문도 스택 형태를 갖추고 있습니다.

마지막에 발생한 에러가 가장 먼저 출력되고, 에러문 맨 끝으로 내려가면 에러의 근원이 출력된 것을 확인할 수 있어요.

개발자들은 문제 발생 출처를 아래에서부터 차근차근 따져봄으로써 에러를 해결할 수 있습니다.

 

요즘은 Chat-GPT나 Claude 등이 워낙 잘 나와 있어서 디버깅 작업이 수월해졌지만, 개발자 커뮤니티(스택오버플로우, 레딧 등)에서 자주 올라오지 않은 생소한 에러들은 여전히 위 방법을 사용해야 합니다...^^

아무래도 생성형 AI가 개발자 커뮤니티 등을 통해 디버깅 방식을 학습하기 때문에 어쩔 수 없는 현상으로 보입니다.

이런 점들을 보면 고전적인 방식도 필요한 경우가 있다고 생각해요!

 

아, 그리고 위에서 언급한 스택오버플로우 커뮤니티에 '스택'이라는 이름이 붙어있지요?

이 커뮤니티 이름도 자료구조 스택의 의미를 따서 지은 것이랍니다!

개발 정보가 가득 쌓이다 못해서 흘러 넘치는 느낌이 들어요ㅎㅎ

 

 

# 스택 ADT 구현 코드 (With 연결 리스트) 

ADT(Abstract Data Type)은 추상적 자료형을 의미합니다.

전반적인 기능 및 동작을 표현하고 싶지만, 구체적이고 엄밀한 과정을 보여줄 필요 없는 경우에 주로 사용해요.

 

자동차로 예시로 들자면... 소비자에게 자동차 기능과 동작 방식만 알려주면 충분하겠죠?

고객에게 엔진이 동작하는 방식, 차량 소프트웨어와 하드웨어가 맞물려서 어떤 식으로 움직이는지 굳이 하나하나 알려줄 필요는 없습니다.

 

ADT는 이런 면에서 비슷하다고 볼 수 있겠네요!

tmi(too much information, 과도한 정보)를 감추고 필요한 부분만 추상적으로 보여주는 것이라고 이해하면 좋습니다.

 

자... 그러면 ADT 형태로 구현한 '스택' 코드를 볼까요?

class Node:
    def __init__(self, item, next):
        self.item = item
        self.next = next
        
class Stack:
    def __init__(self):
        self.last = None
        
    def push(self, item):
        self.last = Node(item, self.last)
        
    def pop(self):
        item = self.last.item
        self.last = self.last.next
        return item
        
if __name__ == "__main__":
    stack = Stack()
    stack.push(0)
    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    stack.push(5)
    
    while stack.last:
        print(stack.pop())

 

연결 리스트를 사용해서 스택을 구현할 것이기 때문에, 먼저 Node 클래스부터 정의해 줍니다.

Node 클래스는 연결 리스트를 구현할 때 많이 사용하는 형태입니다.

item 속성에 값을 저장하고, next 속성에 다음 노드를 연결할 수 있습니다.

연결 리스트 특징에 아주 충실한 속성들입니다!

 

그 다음으로 Stack 클래스를 정의합니다.

Stack 클래스의 last 속성을 통해 가장 최근에 집어넣은 값을 확인할 수 있도록 합니다.

그리고 push 메서드를 통해 item을 집어넣고, pop 메서드를 통해 제일 최근에 넣은 item을 꺼낼 수 있도록 합니다.

 

이렇게 Node 클래스와 Stack 클래스를 정의함으로써 마치 접시를 쌓는 것처럼 item을 관리할 수 있게 됩니다.

위 코드를 동작시키면 0부터 5까지의 숫자를 차례로 넣고, 5부터 0까지 순서대로 꺼내는 모습을 볼 수 있어요!

 

 

# 문제 (20. Valid Parentheses) : 스택 자료구조

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

• Exampe 1
  
  • Input: s = "()"
    Output: true
• Exampe 2 
  • Input: s = "()[]{}"
    Output: true
• Exampe 3 
  • Input: s = "(]"
    Output: false
• Exampe 4
  • Input: s = "([])"
    Output: true

 

올바른 형태로 괄호가 짝을 짓고 있는지 확인하는 문제입니다. 

이 문제는 스택 자료구조로 풀 수 있는 대표적인 문제 유형에 해당해요!

 

문제풀이 코드는 아래와 같습니다.

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

 

가장 먼저 스택을 정의합니다.

Python에서 스택 자료구조를 사용할 때는 추가적인 import 과정이 필요 없습니다.

리스트를 사용하는 것만으로도 충분합니다.

왜냐하면 리스트에서 push, pop 과정을 수행할 때 모두 O(1)에 동작하거든요.

 

그 다음으로 딕셔너리를 정의해 줌으로써, 각각의 닫는 괄호 형태와 매칭되는 여는 괄호를 짝지어 줍니다.

 

이렇게 올바른 괄호인지 확인할 준비를 마쳤습니다.

그 이후부터는 올바른 괄호가 맞는지 확인하기만 하면 됩니다.

 

for 반복문을 통해 입력으로 받은 문자열 s를 하나씩 뜯어서 살펴봅니다.

만약에 딕셔너리 key에 없는 괄호라면 그것은 여는 괄호라는 뜻이겠지요?

여는 괄호에 해당하면 일단 stack에 넣고 봅니다.

 

만약에 딕셔너리 key에 있는 괄호라면 다음 조건들을 따져야 합니다.

+) 참고로 딕셔너리 key에 속한 괄호들은 모두 닫는 괄호에 해당해요.

 

스택이 비어 있는 경우라면, 여는 괄호 없이 다짜고짜 닫는 괄호를 넣겠다는 의미와 같습니다.

따라서 이런 경우는 올바른 괄호라고 보기 어렵기에 False를 반환해줘야 마땅합니다.

 

다음으로 딕셔너리 value가 스택에서 pop 연산으로 뽑아낸 괄호와 다를 때입니다.

소괄호는 소괄호와, 중괄호는 중괄호와, 대괄호는 대괄호와 매칭되어야 하지요?

따라서 이 케이스도 False를 반환해줘야 마땅합니다.

 

마지막 단계에서는 스택에 남아있는 잔여 데이터의 개수를 확인합니다.

올바른 괄호라면 짝을 지은 형태로 모두 pop 연산을 수행했을 것이므로, 남은 데이터가 0일 것입니다.

반대로 올바르지 않은 괄호라면 잔여 데이터가 있을 것이고요.

따라서 스택 내부 데이터 길이가 0이면 True를, 0이 아니면 False를 반환할 수 있도록 설정해야 합니다.

 

 

제출 결과는 위와 같았습니다.

 

 

# 문제 (316. Remove Duplicate Letters) : 스택 자료구조

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

 

• Exampe 1
  
  • Input: s = "bcabc"
    Output: "abc"
• Exampe 2 
  • Input: s = "cbacdcbc"
    Output: "acdb"

 

중복 문자를 제거하되, 사전 순으로 나열했을 시에 가장 앞에 나오는 문자열을 찾는 문제입니다.

위 조건들을 고려하면서 중복된 것들을 제거해야 하는 경우에도 스택 자료구조를 적용하면 좋습니다.

 

문제풀이 코드는 아래와 같습니다.

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        counter, stack, seen = collections.Counter(s), [], set()

        for char in s:
            counter[char] -= 1
            
            if char in seen:
                continue
            
            while stack and char < stack[-1] and counter[stack[-1]] > 0:
                seen.remove(stack.pop())

            seen.add(char)
            stack.append(char)
        
        answer = ''.join(stack)
        return answer

 

중복 문자를 제거해야 하기 때문에 문자가 등장하는 횟수를 체크해야 합니다.

 

이 체크 과정을 수월하게 만들기 위해 colletions 모듈 내부에 있는 Counter 클래스를 사용합니다.

Counter 클래스에 문자열 s를 입력하여 초기화하면, 문자열 s 내부에 있는 알파벳 등장 횟수를 셀 수 있습니다.

 

해당 문제의 조건에 잘 부합하는지 확인하기 위해서 스택 자료구조를 사용합니다.

그리고 스택 내부에 집어넣은 데이터들을 파악하기 위해서 집합 자료형을 정의합니다.

스택 자료구조 용도로 도입한 '리스트' 자료형으로도 in 연산을 사용할 수 있지만, 스택의 추상적인 기능을 부각시키기 위해서 위와 같은 형태로 분리시켰습니다. (원칙적으로 접근하자면 스택 자료구조는 pop, push 연산만 지원해요!)

 

문제를 풀기 위한 준비는 이제 끝났습니다.

 

지금부터는 차례로 s 문자열 내부를 구성하고 있는 문자에 접근해야 합니다.

하나씩 문자에 접근하면서, 확인이 끝난 알파벳의 횟수를 1씩 차감해 줍니다.

알파벳 등장 횟수를 신경써야 하는 문제이므로 이와 같은 과정을 꼭 거쳐야 합니다.

 

만약 현 시점의 문자가 스택 자료구조 속에 포함된 경우라면, 더 볼 필요도 없이 다음 차례 문자로 이동하면 됩니다.

왜냐하면 문제 속에서 중복 문자 사용은 허용하지 않기 때문이죠!

 

그러나 스택 자료구조 속에 해당 문자가 포함되지 않는 경우는 조건을 더 살펴볼 필요가 있겠지요?

이때 스택의 끝 부분에 위치한 데이터가 현 시점의 문자보다 뒷 순서(사전 기준) 에 해당하는지 체크해야 합니다.

 

그리고 이후에도 스택의 끝 부분 데이터가 등장하는지 남은 횟수를 꼭 확인해야 합니다.

이를 확인해야 스택 pop 연산을 수행할 때 후회가 생기지 않거든요.

앞으로 등장할 일이 없는 문자는 절대 제외하면 안 되기 때문에, 반드시 남은 등장 횟수를 체크해야 합니다!

 

이 체크 과정을 모두 끝낸 문자는 집합과 스택에 넣어줍니다.

그래야 다음 문자를 비교할 때 수월해지거든요.

 

문자열의 모든 시점을 확인한 후에는 스택 내부에 남아 있는 데이터들을 하나로 합쳐줍니다.

그러면 그것이 곧 답이 됩니다!

 

 

제출 결과는 위와 같았습니다.

 

 

# 문제 (739. Daily Temperatures) : 스택 자료구조

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

 

• Exampe 1
  
  • Input: temperatures = [73,74,75,71,69,72,76,73]
    Output: [1,1,4,2,1,1,0,0]
• Exampe 2 
  • Input: temperatures = [30,40,50,60]
    Output: [1,1,1,0]

• Exampe 3
  • Input: temperatures = [30,60,90]
    Output: [1,1,0]

 

더 따뜻한 날씨를 위해 며칠을 기다려야 하는지 체크하는 문제입니다.

이 문제도 스택 자료구조를 사용하면 수월하게 해결할 수 있습니다.

 

문제풀이 코드는 아래와 같습니다.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0] * len(temperatures)
        stack = []

        for cur_idx, cur_t in enumerate(temperatures):
            while stack and cur_t > temperatures[stack[-1]]:
                before_idx = stack.pop()
                answer[before_idx] = cur_idx - before_idx
            stack.append(cur_idx)

        return answer

 

먼저 답을 입력할 answer 리스트부터 먼저 정의해 줍니다.

더 따뜻한 날이 없을 경우에는 0을 반환해야 하므로 기본값을 0으로 설정합니다.

 

그 다음으로 스택 자료구조 용도로 사용할 빈 리스트를 정의합니다.

온도가 더 높은 날이 등장하는 순간에 맨 끝에 위치한 데이터를 빼야 하므로, 스택 자료구조를 사용하는 것이 적절합니다.

 

이제 문제를 풀기 위한 모든 세팅이 끝났어요!

지금부터는 기록된 온도 데이터를 하나씩 순서대로 뜯어서 보면 됩니다.

 

우리는 더 따뜻한 날이 오기까지 걸리는 시간이 궁금합니다.

따라서 현재 확인하고 있는 날짜의 온도 데이터가 스택 맨 끝에 위치한 온도 데이터보다 따뜻한지를 확인해야 합니다.

 

만약 이에 해당한다면, 스택에 pop 연산을 취함으로써 맨 끝에 위치한 데이터를 반환합니다. 

반환한 데이터는 이전 데이터의 일자 정보를 담고 있습니다.

문제 내에서 며칠이 걸리는지 확인하는 것을 요구하고 있기 때문에, 현재 일자와 이전 일자 간의 차이를 구해주면 됩니다.

이 값은 answer 리스트의 현재 일자 인덱스에 입력해주세요!

 

스택 체크 과정이 끝난 후, 다음 일자 비교를 위해 현재 정보가 필요하므로 스택 자료구조에 현재 일자를 넣어주면 됩니다.

 

모든 일자를 비교하는 과정을 마쳤으면 answer 리스트를 최종적으로 반환하시면 됩니다.

그게 곧 답이기 때문이지요!

 

 

제출 결과는 위와 같았습니다.

 

---

 

요즘 들어서 컨디션이 점점 좋아지고 있다는 생각이 들어서 기쁩니다 ^_^

이 템포를 유지하기 위해서 지속적인 노력을 해야겠어요!

 

남들보다 오래 방황하고 시간을 쓴 것 같아서 자책을 한 적도 있었지만...

스스로 많이 성장한 것을 느끼고 있는 중이기 때문에 후회는 없습니다!

 

작년에 인연을 맺은 선생님들 간의 교육법 차이, 내적 성찰 및 고뇌 등을 말미암아 더 안정적인 컨디션 운용법을 익히게 된 것 같아요.

 

추상적인 개념의 기본기 다지는 것을 중요시하던 A 선생님... 현실 속 감각을 중요시하던 B 선생님...

두 분의 장점을 흡수해서 이제는 나름 제 방식대로 소화할 수 있게 된 것 같습니다.

 

현실적인 감각을 동원하여 추상적인 개념을 상상하고, 현실 문제에서는 상상 속에서 마주하던 추상적 개념을 발견하는 기쁨을 알게 되었어요.

낯선 것에서 익숙한 개념을 느끼고, 익숙한 것에서 낯선 개념으로 추상화하는 방법도 체득했습니다.

 

역동적인 세상이라 걱정이 앞설 때도 많지만, 저 또한 내면의 역동적인 에너지를 느끼고 있으므로 일단은 즐겨야겠습니다!

올해도 화이팅~~!!!

 

 

+) 해당 포스팅은 '파이썬 알고리즘 인터뷰(저자: 박상길)'를 읽은 후, 제 방식으로 이해한 바를 정리한 글입니다.

++) 부족한 부분이 있으면 댓글로 말씀해 주세요! 겸허한 마음으로 더 공부하고 수정하겠습니다.