스택

한 쪽 끝에서만 자료의 삽입과 삭제가 가능한 자료구조

스택(stack)이란 LIFO(Last In First Out, 후입선출)의 특징을 가지는 자료구조입니다. 후입선출 즉, 나중에 들어온 것이 먼저 나갑니다. 바구니를 연상합시다.

그렇다면 아래 그림을 봅시다. 1, 2, 3을 순서대로 넣은 후, 1을 빼내고 싶을 땐 어떻게 해야할까요?

어쩔 수 없이 3과 2를 차례로 뺀 후에야 1을 빼낼 수 있습니다. 이것이 바로 스택입니다. 가장 나중에 들어온 3이 가장 먼저 나가는 후입선출의 구조죠. 나갈 구멍이 한 쪽밖에 없다고 생각하시면 편합니다.

스택은 리스트로 구현할 수 있고, 내장 함수를 사용하여 쉽게 삽입/반환 등의 연산을 할 수 있습니다.

li = []
li.append(1)    # li == [1]
li.append(2)    # li == [1, 2]
li.pop()        # li == [1]
li.pop()        # li == []

append(값)은 원소 삽입 시에, pop()은 반환 시에 사용하는 함수입니다. 이 두 함수를 사용하여 문제를 풀어보도록 합시다.

연습문제

BOJ 1874

https://www.acmicpc.net/problem/1874www.acmicpc.net

처음에 배열에 들어갈 원소를 하나씩 입력받게 됩니다. 입력받을 때마다 원소를 어떻게 처리할지 판단하는 방식으로 진행해보도록 하겠습니다.

li = []      
ans = []    # '+', '-'를 담을 배열
cnt = 0
flag = True # 불가능한 경우를 위한 flag

li 배열을 사용하여 문제의 과정을 진행하고, ans 배열은 삽입/삭제의 여부에 따라 '+', '-' 기호를 넣어줄 용도로 사용합니다.

입력받은 수열을 만들어 낼 수 없을 때 flag를 통해 예외처리를 해줄 예정입니다.

n = int(input())
li = []     
ans = []    
cnt = 0
flag = True
for _ in range(n):
    val = int(input())

    while cnt < val:
        cnt += 1
        li.append(cnt)
        ans.append('+')
    if li[-1] == val:
        li.pop()
        ans.append('-')
    else:
        flag = False
        break

if flag == True:
    print('\n'.join(ans))
else:
    print('NO')

cnt 변수는 append() 할지 말지를 결정하는 지표가 됩니다.

입력값이 나올 때까지 수를 삽입하다가, 그 수가 나오면 삭제하는 과정을 반복하면 됩니다.

풀어볼 문제

스택의 성질을 응용해서 아래의 문제들을 풀어봅시다 !

https://school.programmers.co.kr/learn/courses/30/lessons/12909school.programmers.co.kr

[프로그래머스] 올바른 괄호

https://www.acmicpc.net/problem/17298www.acmicpc.net

[백준] 오큰수

https://www.acmicpc.net/problem/12789www.acmicpc.net

[백준] 도키도키 간식드리미