스택 - 바킹독 유튜브

스택의 정의

• 한 쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조
• 먼저 들어간 요소가 나중에 나오는 구조
• FILO

스택의 성질

• 원소추가가 O(1)
• 원소제거가 O(1)
• 제일 상단의 원소 확인이 O(1)
• 제일 상단이 아닌 나머지 원소들의 확인/변경이 ‘원칙적’으로 불가능
• 스택문제를 보면 원소의 추가, 제거, 상단의 원소 확인 기능만을 필요로 한다.

연습문제

boj-10828

import sys
iter_num = int(sys.stdin.readline())
stack = []
for _ in range(iter_num):
    operator = sys.stdin.readline().split()
    if operator[0] == 'push':
        stack.append(int(operator[1]))
    elif operator[0] == 'top':
        try:
            print(stack[-1])
        except:
            print(-1)
    elif operator[0] == 'pop':
        try:
            print(stack.pop())
        except:
            print(-1)
    elif operator[0] == 'size':
        print(len(stack))
    else:
        print(int(len(stack) == 0))

boj-10773

import sys
input = sys.stdin.readline

K = int(input().rstrip())
stack = []

for _ in range(K):
    cur_num = int(input().rstrip())
    if cur_num == 0:
        stack.pop()
        continue
    stack.append(cur_num)

if len(stack) == 0: print(0)
else: print(sum(stack))

boj-1874

import sys
input = sys.stdin.readline

N = int(input().rstrip())
stack = []
answer = ""
numbers = [x for x in range(1, N+1)][::-1]
for _ in range(N):
    cur_num = int(input().rstrip())
    while numbers and stack[-1:] != [cur_num]:
        stack.append(numbers.pop())
        answer+= "+"
    if stack[-1:] != [cur_num]:
        print("NO")
        sys.exit(0)
    stack.pop()
    answer +="-"
for value in answer:
    print(value)

# 개선버전

import sys
input = sys.stdin.readline

N = int(input().rstrip())
cnt = 1
answer = ""
stack = []
while N:
    cur_num = int(input().rstrip())
    while cnt <= cur_num:
        stack.append(cnt)
        cnt+=1
        answer += "+\n"
    if stack[-1] != cur_num:
        print("NO")
        sys.exit(0)
    stack.pop()
    answer += "-\n"
    N-=1
print(answer)

피드백

조금 어려워보이는 문제도 풀이를 생각해낼 수 있는 힘이 생긴 것 같다.

스택문제를 보면 원소의 추가, 제거, 상단의 원소 확인 기능만을 필요로 한다

이 부분을 통해서 스택에 대한 이해도가 높아졌다. 리스트의 기능을 최대한으로 활용해서 풀려고만 했는데 앞으로 스택문제는 기본에 더 충실해서 top값, stack의 pop, 마지막에 값을 넣어주는 Push 이 세가지에만 집중해서 풀어야겠다.

목표문제 boj-3015