문자열 반전
스택의 데이터를 역순으로 정렬하거나 검색할 때 사용할 수 있다. 7-1 에서 구현한 스택 클래스를 써서 구현해보자.
내 정답:
from stack import Stack
def reverse_string_with_stack(string):
s = Stack()
result = ''
for i in string:
s.push(i)
while not s.isEmpty():
result += s.pop()
return result
print(reverse_string_with_stack('Hello World!'))
결과
PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/7. 추상 데이터 타입/eg_stack_reverse_string.py"
!dlroW olleH
괄호의 짝 확인하기
스택을 사용하면 괄호의 균형이 맞는지 (여는 괄호와 닫는 괄호의 수가 일치하는지) 쉽게 확인할 수 있다.
내 정답:
from stack import Stack
def balance_parenthesis(string):
s = Stack()
count = 0
for i in string:
s.push(i)
while not s.isEmpty():
if s.peek() == ')':
s.pop()
count += 1
continue
else:
break
return count == s.size()
print(balance_parenthesis('(()))'))
print(balance_parenthesis('((()))'))
print(balance_parenthesis('(((())'))
책의 정답:
def balance_parenthesis_book_answer(string):
s = Stack()
balanced = True
index = 0
while index < len(string) and balanced:
symbol = string[index]
if symbol == '(': # '(' 가 들어오면 스택에 넣는다.
s.push(symbol)
else: # ')' 가 들어오면 둘 중 하나
if s.isEmpty(): # 비어 있다면 (즉 '(' 의 수보다 ')' 의 수가 더 많다면)
balanced = False
else: # 아니라면 그냥 '(' 를 스택에서 하나 없애준다.
s.pop()
index += 1
if balanced and s.isEmpty():
return True
else:
return False
결과
PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/7. 추상 데이터 타입/eg_stack_balance_parenthesis.py"
False
True
False
책의 정답이 더 완벽한 정답이다. 나의 코드는 괄호가 조금만 벗어나도 예를 들어 ((()())) 이런 식으로 되어있다면 괄호가 밸런스 되어있지 않는다고 뜨지만, 실제로는 밸런스 되어있다. 따라서 이와 같이 새로운 답을 작성했다.
def balance_parenthesis(string):
s = Stack()
for i in string:
if i == '(':
s.push(i)
else:
if s.isEmpty():
return False
s.pop()
return s.isEmpty()
'(' 가 있을 때 마다 스택에 넣어주고, 아니라면 스택의 '(' 를 하나씩 빼준다. 허나 빼줄 '(' 가 없다면, 이는 ')' 의 개수가 더 많다는 의미이므로 False 를 반환한다. 모든 작업이 끝난 후, 스택에 '(' 가 남아있다면 이는 '(' 의 개수가 더 많다는 의미이므로 마찬가지로 False 를 반환하면 된다. 이를 s.isEmpty() 로 반환하는 것으로 마무리했다.
10진수를 2진수로 변환
스택을 사용하여 10진수를 2진수로 변환해보자. 나는 2진수 대신 그냥 n진수로 바꿔주도록 만들었다. 방법은 wikiHow의 진법 변환을 참고했다.
내 정답:
from stack import Stack
def decimal_to_nth(number, n):
s = Stack()
num = number
result = ''
while num >= n:
s.push(num % n)
num = num // n
s.push(num)
while not s.isEmpty():
result += str(s.pop())
return result
print(decimal_to_nth(30, 2))
print(decimal_to_nth(37, 3))
결과
PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/7. 추상 데이터 타입/eg_stack_decimal_to_binary.py"
11110
1101
스택에서 최솟값 O(1)로 조회
스택에서 최솟값을 모든 요소의 조회가 아닌 O(1)로 조회하는 방법은 없을까?
from stack import Stack
class NodeWithMin(object):
def __init__(self, value=None, minimum=None):
self.value = value
self.minimum = minimum
class StackMin(Stack):
def __init__(self):
self.items = []
self.minimum = None
def push(self, value):
if self.isEmpty() or self.minimum > value:
self.minimum = value
self.items.append(NodeWithMin(value, self.minimum))
def peek(self):
return self.items[-1].value
def peekMinimum(self):
return self.items[-1].minimum
def pop(self):
item = self.items.pop()
if item:
if item.value == self.minimum:
self.minimum = self.peekMinimum()
return item.value
else:
print("Stack is empty.")
def __repr__(self):
aux = []
for i in self.items:
aux.append(i.value)
return repr(aux)
s = StackMin()
for i in range(10, 0, -1):
s.push(i)
print(s)
print(s.peekMinimum())
위와 같은 방식을 사용하면 스택의 각 아이템이 곧 노드로써, 자신의 값과 자신이 append 될 당시 가장 작은 값이었던 아이템의 값을 minimum으로 기억한다. 스택은 어차피 후입선출 구조이기 때문에, 자신이 append 될 당시 가장 작은 값은 무조건 적으로 자신이 pop 될 때 가장 작은 값이다. 또한 이를 append 될 때 마다 현재 존재하는 minimum 값과 비교하여 계속하여 바꿔주므로, 가장 작은 값은 append나 pop 될 때 계속하여 갱신된다.
스택 집합
스택에 '용량'이 정해져 있다고 하자. 한 스택의 용량이 초과하면 새 스택을 만들어야 한다. 이 경우 여러 스택이 있게 될 텐데, 이 스택 집합에서도 단일 스택과 같이 push() 와 pop() 메서드를 사용하려면 어떻게 해야할까?
내 정답:
from stack import Stack
class SetOfStacks(object):
def __init__(self, sizeEachStack):
self.sets = []
self.sizeEachStack = sizeEachStack
def isEmpty(self):
return not bool(self.sets)
def push(self, value):
length = len(self.sets)
if length:
if self.sets[length-1].size() == self.sizeEachStack:
self.sets.append(Stack())
self.sets[length].push(value)
else:
self.sets[length-1].push(value)
else:
self.sets.append(Stack())
self.sets[0].push(value)
def pop(self):
length = len(self.sets)
if length:
if not self.sets[length-1].isEmpty():
return self.sets[length-1].pop()
else:
self.sets.pop()
else:
print("Stack Set is empty.")
def size(self):
size = 0
for i in self.sets:
size += i.size()
return size
def peek(self):
length = len(self.sets)
if length:
return self.sets[length-1].peek()
else:
print("Stack Set is empty.")
def __repr__(self):
return repr(self.sets)
s = SetOfStacks(10)
for i in range(30):
s.push(i)
print(s)
while not s.isEmpty():
s.pop()
print(s)
결과
PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/7. 추상 데이터 타입/eg_stack_set_stacks.py"
[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [10, 11, 12, 13, 14, 15, 16, 17, 18, 19], [20, 21, 22, 23, 24, 25, 26, 27, 28, 29]]
[]
출처
파이썬 자료구조와 알고리즘 - 한빛미디어, 미아 스타인
'Python > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 9-2. 로그 선형 정렬, 고급정렬 (Log-linear Sorting, Advanced Sorting) (0) | 2020.08.07 |
|---|---|
| 9-1. 2차 정렬과 선형 정렬 (Quadratic and Linear Sorting) : 파이썬 자료구조와 알고리즘 (0) | 2020.08.06 |
| 8. 점근적 분석 (Asymptotic Analysis): 파이썬 자료구조와 알고리즘 (0) | 2020.08.04 |
| 7-2-2. 큐, 우선순위 큐, 힙, 연결 리스트 예제 (Other Types Examples): 파이썬 자료구조와 알고리즘 (0) | 2020.08.03 |
| 7-1. 추상 데이터 타입 (Abstract Data Type): 파이썬 자료구조와 알고리즘 (0) | 2020.08.02 |
