[Python] 자료구조: 스택(Stack) / 예제로 알아보기

 

0. 들어가기 전

 

2020/08/18 - [코딩/자료구조] - [Python] 자료구조: 스택(Stack) / LIFO

[Python] 자료구조: 스택(Stack) / LIFO

이번 포스트에서는 기본적인 개념에 대해서는 설명하지 않고, 간단한 예시를 통해 어떻게 쓰일 수 있는지를 정리하고자 한다.  

 

스택구조가 어떻게 구현됐는지와 O(n)이 나오는지를 유의하며 보자.

---

1. 클래스 정의 

 

class Stack:
    def __init__(self):
        self.box = []
	     
    def push(self, item):
        self.box.append(item)

    def pop(self):
        return self.box.pop()

    def top(self):
        return self.box[-1]

    def size(self):
        return len(self.box) 

스택 구조의 기본적인 기능을 담고 있는 클래스를 선언하였다. 이 클래스를 기본으로 사용한다는 전제 하에 예시를 알아볼 것이다.

 

---

 

2. 십진법을 이진법으로 바꾸기 (Decimal to Binary)

 

108의 경우 십진법으로 바꾸면  1*64 + 1* 32 + 1*8 + 1*4, 즉 1101100으로 바꿀 수 있다. 

다음과 같은 방식으로 몫이 0이 나올 때까지 2로 계속 나눈다고 생각했을 때, 나머지가 순서대로 0011011 가 나온다. 이를 뒤집으면 그 108의 이진법 표현이 된다. 108뿐 아니라 다른 숫자에도 적용이 가능하다.

 

'순서대로' 나온 결과(나머지 값)를 '뒤집으면' 구하고자 하는 값이 된다는 점에서 스택 구조를 이용하면 간단하게 값을 구할 수 있다. 

 

def dec_2_bin(dec_number):
    r_stack = Stack()

    while dec_number > 0:
        r = dec_number % 2 
        r_stack.push(r) 
        dec_number = dec_number // 2
    bin_string = ""
    while r_stack.size() != 0:
        bin_string = bin_string + str(r_stack.pop()) 
    return bin_string 
    
print(dec_2_bin(108)) # 1101100
print(dec_2_bin(63))  # 111111 

 

---

3. bracket balance check

괄호의 열림과 닫힘이 잘 매칭이 되는지를 체크하는 문제다. 

가장 기본적으로 소괄호만 있다는 가정하에 코드를 짰다.

실제로는 사칙연산같은 수학연산이나 중괄호, 대괄호도 쓰일 수 있다. 이 코드에서 조건문을 수정 및 추가하면 구현할 수 있다.

def bracket_checker(string:str):
    checker = Stack()
    for ch in string:
        if ch != ')':
            checker.push(ch) 
        else:
            if checker.size() != 0:
                checker.pop()
            else:
                return False
    if checker.size() != 0:
        return False
    else:
        return True
        
true_example = ['((()))', '(()()())', '((())(()))','()']
false_example = ['((()', '(()()())))', '()))','()))())']

result1 = [bracket_checker(i) for i in true_example]
print(result1)

result2 = [bracket_checker(i) for i in false_example]
print(result2) 

 

닫는 소괄호가 아닐 경우, (지금 조건에서는 열린 소괄호일 때) 스택에 넣는다. 닫는 소괄호일 때 스택에서 가장 위를 뺀다. 여기서 빠지는 아이템은 닫는 소괄호 앞에 있는 여는 소괄호일 것이다. 괄호가 중첩되든 여러 개가 있든 이런 식으로 빼다보면 소괄호끼리 매칭이 되면 (balanced)하면 결과적으로는 스택에 쌓여있는게 없게 되므로 True, 아니면 False가 나올 것이다.