Stack
말 그대로 쌓아 올린다
내가 책더미에 책을 추가하고 싶으면 맨 위에 올리고 = push
원하는 책을 빼고 싶을 때에도 맨 위에서부터 차례로 빼는 = pop
이걸 FILO(Firs In Last Out)이라고 표현 = 선입후출
python에서는 stack을 제공하지 않기 때문에 대안으로 list의 append나 push로 스택을 대체하거나 deque를 응용해서 stack처럼 사용함
그러니까 stack이 실제로 존재하는 자료형은 아님!
하하 그러니까 정리하면
python에는 stack이 없어
그래서 stack을 쓰고 싶으면 네가 구현해야돼
stack은 ADT(Abstract Data Type)으로 실제 자료형으로 있는게 아닌
추상자료형!
Stack의 구현
stack에서는 어떤 연산이 있어야 할까?
- push
- pop
- isFull
- isEmpty
- top
stack = []
max_size = 10
def push(stack, item):
if isFull(stack):
print('stack이 가득 찼습니다')
else:
stack.append(item)
def pop(stack):
if isEmpty(stack):
print('stack이 비어있습니다')
return None
else: return stack.pop()
def isFull(stack):
return len(stack) == max_size
def isEmpty(stack):
return len(stack)==0
더 쉽게쉽게 발전시켜보면?
stack = []
# stack push = list append
# stack pop = list pop
문제 08. 괄호 짝 맞추기
내가 푼 답 :
def solution(strings):
begin = 0
end = 0
for string in strings:
if string == '(':
begin += 1
elif string == ')':
end += 1
if begin < end:
return False
if begin == end:
return True
else: return False내가 stack으로 풀려고 노력해서 푼 답:
def solution(strings):
stack = []
for string in strings:
if string == "(":
stack.append(1)
else:
try:
stack.pop()
except:
return False
if len(stack) == 0:
return True
else: return False문제 09. 10진수를 2진수로 변환하기
내가 한 것:
def solution(number):
# 10 = 2**3 + 2**1
# 10 = 5*2 = (2*2 + 1) *2
stack = []
done = True
while done:
if number // 2 == 0:
done = False
else:
stack.append(number % 2)
number = number // 2
stack.append(1)
stack = stack[::-1]
return stack
## list 묶음을 어떻게 string으로 만들지..내가 한 것 ver2:
def solution(number):
# 10 = 2**3 + 2**1
# 10 = 5*2 = (2*2 + 1) *2
result = ''
while number // 2 != 0:
result += str(number % 2)
number = number // 2
result += '1'
result = result[::-1]
return result문제 10. 괄호 회전하기
def correct_case(question):
# small bracket : ()
# medium bracket : []
# large bracket : {}
stack = []
for candid in question:
if candid == "(" or "{" or "[":
stack.append(candid)
else:
if not stack:
return False
elif (candid == ")") and (stack[-1] == "("):
stack.pop()
elif (candid == "]") and (stack[-1] == "["):
stack.pop()
elif (candid == "}") and (stack[-1] == "{"):
stack.pop()
else: return False
if stack: return False
else: return True
def rotate_string(string):
return string[1:]+string[0]
def solution(s):
result = 0
for x in range(len(s)):
if correct_case(s): result += 1
s = rotate_string(s)
return result
문제 11. 짝지어 제거하기
내가 쓴 답
def solution(s):
stack = []
for alphabet in s:
if len(stack) == 0:
stack.append(alphabet)
elif stack[-1] == alphabet:
stack.pop()
else:
stack.append(alphabet)
return 1 if len(stack) == 0 else 0내가 아쉬운 점
True/False boolen을 반납하는 함수의 활용
def solution(s):
stack = []
for a in s:
if stack and stack[-1] == a:
stack.pop()
else:
stack.append(a)
return int(not stack)문제 12. 주식 가격
내가 한 것
def solution(prices):
answer = [0] * len(prices)
for i in range(len(prices)):
day = 0
for future_price in prices[i+1:]:
if future_price >= prices[i]:
day+=1
answer[i] = day
return answer 시간복잡도가 지금 O(N^2)임
그래서 이 문제의 답이 될 수 없고 stack을 활용하지도 않았음
이렇게 푸는 방식에서 불필요한 연산을 줄여 효율성을 확인해야함
그리고 일단 나 문제 잘못이해함 :> 다시 해보자
문제 13. 크레인 인형 뽑기 게임
내가 한 것
import numpy as np
def solution(board, moves):
board = np.array(board).T
result = 0
stack = [0]
for move in moves:
for idx, doll in enumerate(board[move-1]):
if doll != 0:
board[move-1][idx] = 0
if stack[-1] != doll:
stack.append(doll)
else:
stack.pop()
result += 1
break
return result*2문제 14. 표 편집
내가 한 것:
def solution(n, k, cmd):
result = ["X"]*n
info = list(range(n))
backup = []
for command in cmd:
if command.startswith('U'):
_, stair = command.split(' ')
k -= int(stair)
elif command.startswith('D'):
_, stair = command.split(' ')
k += int(stair)
elif command.startswith('C'):
backup.append(info.copy())
candid = info[k]
info.remove(candid)
if k > len(info):
k = len(info)
elif command.startswith('Z'):
info = backup.pop()
else: print('wrong command')
for mem in info:
result[mem] = 'O'
return ''.join(result)내가 못한 것: stack의 활용
직접 배열을 계속 살려서 가져가면 시간이 많이 듬
특히 remove가 생각보다 시간을 오래 쓰는 것 같음 한바퀴를 돌아서 찾는 것 같음
답지에서는 순서를 기억해서 쓰는 방식으로 배열을 건드리지 않으며 효율을 높임
답지:
우주대귀욤