스택(stack)
스택(stack)은 '쌓아놓은 더미'라고 하는데 과자 프링글스를 생각하면 좋다.
가장 먼저 들어간 과자는 맨 마지막에 나올 수 있고
가능 늦게 들어간 과자는 가장 먼저 나올 수 있다.
이처럼 데이터도 프링글스 과자와 같다.
재귀함수는 다른 함수들을 이해하기 위해서는 스택을 이해하고 넘어가야 한다.
스택의 추상데이터는 암기해 두고 알고리즘 문제를 풀며 점차 이해도를 높여가야겠다.
__init__ : 스텍을 초기화
push() : 아이템 추가
pop(): 아이템 제거 및 출력
peek() : 맨위의 요소 삭제 안 하고 반환
is_empty : 스택여부를 혹인하고 Ture or False 반환
size() : 아이템 개수 봔환
스택 문제
"""
- 스택 문제 1
- 키보드 Backspace 기능 구현
- input_string = ‘123//45/6789///’
- /를 만나면 앞의 값을 삭제
- 참고 - 맨앞에 /만나면 어떻게 처리해야 되는지 생각 해보기
- answer = ‘146’
"""
def backspace_string(input_string):
stack = []
for i in input_string:
if i == '/':
if len(stack) > 0:
if stack:
stack.pop()
else:
stack.append(i)
return ''.join(stack)
print(backspace_string("123//45/6789///"))
print(backspace_string("/987////65/432//1/"))
키보드의 backspace를 구현 한 문제이다.
처음에. pop()의 사용방법을 잘 몰라 구글에 검색하고서야 진행이 가능했다.
하지만 문제가 두 번제 에시 출력 문자열의 시작이 '/'로 시작한다.
if stack:
stack.pop()첫 if문에서 한 번 더 걸러 주는 위와 같은 조건문을 사용하지 않으면
아래와 같은 에러가 발생한다.
IndexError: pop from empty list
list에 아무것도 없는데 어떻게 리시트의 값을 pop 하냐 이다.
그래서 위와 같은 if문을 사용해 줘 stack이 False이라면 pop 하지 말라는 조건문을 넣어 줬다.
if len(stack) > 0:
이런 식으로도 풀이가 가능한데
list의 구조를 이용한다면 stack = [''] 안에 아무것도 없는 배열이기 때문에 False이 된다.
마무리
튜터님이 자료형의 이해를 높여야 한다고 하셨는데 이번 문제를 풀며 더욱 뼈저리게 느끼게 됐다.
자료형과 스택, 재귀함수 등 먼저 이해도를 높여야겠다.