[백준BOJ] 단계별로 문제풀기 - 스택 정답 및 후기(파이썬, python)

백준 알고리즘에서 제공되는 문제들 중 단계별로 문제 풀기 - 스택 1번~6번을 파이썬으로 풀어보았다. 스택 6문제 모두 깃허브에 올려놓았다. 푼지는 좀 됐는데 포스팅이 늦었다... ㅠㅠ

 

www.acmicpc.net/step/11

스택 단계

원본 코드는 깃허브에!!

tomy9729/Algorithm

 

0. 스택

스택은 대표적인 자료구조 중 하나다. Last-IN-First-Out 즉 후입 선출의 특징을 가지는 자료구조이다. 바구니에 물건을 담는다고 생각해보자. 바구니에는 물건이 아래서부터 차곡차곡 쌓인다. 바구니에 담은 물건을 다시 뺄 때 가장 마지막에 넣은 물건을 가장 먼저 빼게 된다. 바구니가 스택과 같은 특징을 보인다! 

가장 위에 담은 물건부터 빼야한다.

스택에 데이터를 넣는 것을 push, 데이터를 삭제하는 것은 pop이라고 한다. 스택에서 가장 위에 있는 데이터를 top이라고 하며 push되거나 pop이 되는 위치는 항상 top이어야 한다. push와 pop이 가장 주요한 함수이며 top의 위치를 읽는 peek함수도 존재한다.

 

스택은 배열과 연결리스트로 구현할 수 있다. 둘 다 장단점이 존재한다. 배열로 구현할 경우 원하는 데이터의 접근 속도가 빠르다는 장점이 있다. 그러나 데이터 최대 개수를 미리 정해놔야 한다는 단점이 있다. 만약 배열의 크기보다 많은 데이터를 push 할 경우 스택의 크기를 재조정해줘야 한다. 또한 중간에 위치한 데이터를 삽입, 삭제가 매우 비효율 적이다. 연결 리스트로 구현할 경우 데이터의 최대 개수가 제한적이지 않고 중간 데이터에 대한 삽입, 삭제가 효율적이다. 그러나 원하는 데이터에 접근하기 위해서는 반드시 연결 리스트를 따라 이동해야 하기 때문에 배열보다 오래 걸린다. 

 

단계별로 문제풀기에서는 배열로 구현하는 것이 더 효율적이라고 판단하여 모든 문제를 배열로 구현한 스택으로 풀었으며 이처럼 경우에 따라 배열로 구현할지, 연결 리스트로 구현할지 고민하여 더 효율적인 방법을 선택하면 된다. 

---

 

1. 10828번 스택

문제
정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.
push X: 정수 X를 스택에 넣는 연산이다.
pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 스택에 들어있는 정수의 개수를 출력한다.
empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

스택과 스택을 구성하는 가장 기본적인 함수들을 구현하는 문제이다. 총 다섯 개로 push, pop, size, empty, top(peek)이다. 파이썬에서는 배열 자체에서 지원하는 함수가 스택과 유사한 점이 많기 때문에 비교적 쉽게 구현할 수 있다. 하나의 빈 배열을 만들고 그 자체를 스택으로 사용한다. 바구니를 옆으로 눕혔다고 상상해보자. 배열과 매우 유사한 형태이다. push는 배열의 append함수로 구현할 수 있다. 배열로 구현한 스택의 push는 가장 먼저 비워져 있는 배열에 데이터를 넣어야 한다. 만약 배열이 이미 가득 차있다면 append 함수를 통해 배열 마지막에 원소를 추가할 수 있다. 파이썬에서는 배열의 크기를 정해놓지 않고 append를 통해 스택의 push를 구현할 수 있다.

스택의 pop은 파이썬 배열의 함수 pop과 완전 동일하다. 파이썬 배열의 함수 pop은 배열의 마지막 원소를 반환하고 삭제하는 것인데 스택의 pop 또한 그렇다. 

배열의 크기는 정해져 있지 않으며 배열의 크기가 바로 스택의 크기이다. size는 배열의 길이를 그대로 반환하면 된다.

empty도 마찬가지이다. 배열의 길이가 0이라면 empty이다.

top의 경우 배열의 마지막 원소를 출력하면된다. 

#10828번 스택
import sys
input = sys.stdin.readline
n = int(input())
stack = []
for i in range(n) : 
  command = input()[:-1] # sys.stdin.readline는 개행까지 포함한 문자열을 넘겨준다. 마지막 개행문자를 삭제
  if command[0:4] == 'push' : #push X: 정수 X를 스택에 넣는 연산이다.
    stack.append(int(command[5:]))
  elif command == 'pop' : #pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
    if len(stack) == 0 : 
      print(-1)
    else : 
      print(stack.pop())
  elif command == 'size' : 
    print(len(stack)) #size: 스택에 들어있는 정수의 개수를 출력한다.
  elif command == 'empty' :  #empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
    if len(stack) : 
      print(0)
    else : 
      print(1)
  elif command == 'top' : #top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
    if len(stack) == 0 : 
      print(-1)
    else : 
      print(stack[len(stack)-1])
  else : 
    continue

---

 

2. 10773번 제로

문제
나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.
재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.
재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.
재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

우선 입력되는 숫자를 스택에 push 한다. 그리고 0이 나올 때마다 스택에서 pop을 한다. 최종적으로 스택에 남아 있는 모든 수의 합을 출력한다.

#10773번 제로
k = int(input())
stack = []
for i in range(k) : 
  num = int(input())
  if num == 0 : 
    stack.pop()
  else : 
    stack.append(num)
print(sum(stack))

---

 

3. 9012번 괄호

문제
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’와 ‘)’ 만으로 구성되어 있는 문자열이다. 그중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 
여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO로 나타내어야 한다.

입력받은 문자열이 VPS인지 아닌지 확인해야한다. VPS의 조건이 복잡해 보일 수도 있지만 생각보다 쉬운 문제이다. 우리가 유의해야 할 문자는 '('와 ')'이며 모든 괄호가 '()'과 같이 한 쌍을 이룬다면 이 문자열은 VPS이다. 문자열을 입력받으면 한 문자씩 스택에 push 한다. 문자를 push 할 때마다 스택의 top과 그 전 문자가 '()' 괄호 한 쌍을 이루는지 확인한다. 만약 괄호 한 쌍을 이룬다면 쌍을 이룬 '('과 ')'는 스택에서 제거한다. 문자열의 끝까지 push 하고 앞선 규칙을 반복했을 때 스택이 empty라면 VPS이고 스택이 empty가 아니라면 VPS가 아니다. 

#9012번 괄호
t = int(input())
for i in range(t) : 
  parentheses = input()
  stack = []
  for j in range(len(parentheses)) : 
    stack.append(parentheses[j]) # 스택에 괄호를 하나씩 넣어준다
    if len(stack) > 1 :
      if stack[-2] == '(' and stack[-1] == ')' : #괄호가 완성되면 스택에서 괄호 삭제
        stack.pop()
        stack.pop()
  if len(stack) == 0 : #최종적으로 스택에 아무것도 없으면 YES
    print("YES")
  else : 
    print("NO")   

---

 

4. 4949번 균형잡힌 세상

문제
세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.
정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.
문자열에 포함되는 괄호는 소괄호("()")와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

- 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
- 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
- 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
- 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
- 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

3번과 비슷하면서도 더 어려워보이지만 문제를 해결하는 방법은 같은 원리이다. 우선 괄호의 종류가 두 가지이며, 괄호 사이에 있는 문자열도 균형이 잡혀야 하는 게 가장 중요한 규칙이다. 처음에는 '()', '[]'에 대해 따로 스택을 사용해 문제를 해결해야했다. 그러나 '([)]'와 같이 균형이 잡히지 않는 문자열도 균형 잡힌 문자열로 분류하는 문제가 발생했다. 해결방법은 간단하다. '()'과 '[]' 모두 한 스택에서 균형 잡힘 여부를 판단하면 된다. 입력받은 문자열에 대해서 '(', ')', '[', ']'만 스택에 push 한다. push 할 때마다 top과 그 전 문자가 '()' 또는 '[]'일 경우 쌍을 이루는 두 문자를 pop 한다. 문자열 끝까지 이 과정을 반복하고 최종적으로 스택이 empty라면 균형 잡힌 문자열이다. 

#4949번 균형잡힌 세상
parentheses = input()
while parentheses != '.' : 
  stack = []
  for j in range(len(parentheses)) : 
    if parentheses[j] == '(' or parentheses[j] == ')' or parentheses[j] == '[' or parentheses[j] == ']'  :
      stack.append(parentheses[j]) # 스택에 괄호를 하나씩 넣어준다
    if len(stack) > 1 :
      if stack[-2] == '(' and stack[-1] == ')' : #괄호가 완성되면 스택에서 괄호 삭제
        stack.pop()
        stack.pop()
      elif stack[-2] == '[' and stack[-1] == ']' : #괄호가 완성되면 스택에서 괄호 삭제
        stack.pop()
        stack.pop()
  if len(stack) == 0 : 
    print("yes")
  else : 
    print("no")
  parentheses = input()

---

 

5. 1874번 스택 수열

문제
스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

문제가 조금 이해하기 어려울 수 있다. 스택에는 반드시 1부터 n까지 오름차순으로 push해야 한다. 만약 n이 5라면 스택에 push 하는 순서는 반드시 1,2,3,4,5이다. 수열은 이 스택에서 pop을 통해 뽑은 숫자로 만드는 것이다. 또 한 수열은 입력을 통해 주어진다. 예를 들어 n은 5이고 주어진 수열이 5,4,3,2,1이라면 push를 5번 수행하고 pop을 5번 수행하여 수열을 만들 수 있다. 

먼저 스택으로 사용할 배열 stack을 선언하고, push,pop 여부를 저장할 pushpop 배열을 선언했다. num은 스택에 몇까지 push 됐는지 저장하기 위한 변수이며 fail은 가능한 경우와 불가능한 경우를 구분하기 위해 선언했다. 

수열에 대해서 i번 째 숫자를 배치할 차례라고 가정해보자. 만약 i번 째 숫자가 i-1번째 숫자보다 크다면 일단 스택에 i번째 숫자까지 push 해야 한다. i번 째 숫자까지 push 하고 i번 째 숫자를 배치하기 위해 pop 하기 때문이다. 만약 i번 째 숫자가 i-1번째 숫자보다 작다면 수열을 만들기 위해서는 스택에서 top에 있는 숫자와 i번 째 숫자가 같아야 한다. 스택에서는 무조건적으로 pop을 할 수밖에 없는데 만약 이 숫자가 i번 째 숫자와 다르다면 이 수열은 만들 수 없는 수열이기 때문이다. 이 경우 fail을 1로 초기화하여 NO를 출력하도록 한다. 만약 fail이 0이라면 push와 pop이 일어날 때마다 push 할 때는 '+'를, pop 할 때는 '-'를 입력한 pushpop 배열을 출력한다. 

#1874번 스택 수열
n = int(input())
stack = [] # 1~n까지 순서대로 push될 스택
pushpop = [] # push는+, pop은- 가 입력될 배열
num = 1 # 입력되는 숫자가 몇인지 저장
fail = 0 # 실패 시 1로 저장
for i in range(n):
  temp = int(input()) # i번 째에 입력되야할 배열의 숫자
  for j in range(num,temp+1) : # temp까지 스택에 push
    stack.append(j)
    pushpop.append('+')
    num += 1 # push할 때마다 입력되는 숫자 1씩 증가
  if stack[-1] == temp : # i번 째 입력되야할 배열의 숫자가 top이라면 pop
    stack.pop()
    pushpop.append('-')
  else : 
    fail = 1

if fail : 
  print('NO')
else:
  for i in range(len(pushpop)) : 
    print(pushpop[i])

---

 

6. 17298번 오큰수

문제
크기가 N인 수열 $A = A_1, A_2, ..., A_N$이 있다. 수열의 각 원소 $A_i$에 대해서 오큰수 $NGE(i)$를 구하려고 한다. $A_i$의 오큰수는 오른쪽에 있으면서 $A_i$보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.
예를 들어, $A = [3, 5, 2, 7]$인 경우 $NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1$이다. $A = [9, 5, 4, 8]$인 경우에는 $NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1$이다.

문제 자체는 2중 반복문을 통해 쉽게 구현할 수 있다. 그러나 이는 O(n^2)으로 비효율적이며 스택을 활용하면 좀 더 빠르게 문제를 해결할 수 있다. 먼저 오큰수의 정의를 정확히 이해해야 한다. 오큰수란 i번 째 원소를 기준으로 오른쪽에 있는 원소들 중 가장 먼저 i번 째 원소보다 큰 수를 말한다. 가장 이상적인 경우는 i+1번째 수가 오큰수인 경우이다.

nums는 주어진 수열을 저장하는 배열이며 nge는 각 수열에 대해 오 큰 수를 저장한다. 스택에는 i+1번 째 수가 오큰수가 아닌 원소들의 index, 즉 i를 저장한다. i번 째 수에 대해 i+1번 째 수가 오큰수가 아니어서 스택에 i가 push 됐다고 가정하자. i번 째 수의 오큰수는 제쳐두고 일단 반복문을 돌아간다. 반복문을 도는 과정에서 i+2번 째 수가 i번 째 수보다 큰지 확인한다. 만약 더 크다면 i+2번 째수가 i번 째 수의 오큰수가 되는 것이다. i번 째 수의 오큰수를 찾았으므로 i를 스택에서 pop한다. 만약 i+2번 째수도 오큰수가 아니라면 i+3번 째수와 비교해야 한다. 모든 반복문을 돌고도 스택에 남아있는 index들은 오큰수가 없음을 의미한다. 전부 -1로 저장한다. 

스택을 활용한 문제 중 어려운 문제에 속하며 아이디어를 생각하는데 꽤 오래 걸렸다. 스택 문제를 연습하는데 좋은 문제라고 생각한다. 

#17298번 오큰수
n = int(input())
nums = list(map(int,input().split()))
stack = []
nge = [0]*(n-1)
for i in range(n-1):
  if nums[i] < nums[i+1] : 
   nge[i] = nums[i+1] # 바로 오른쪽에 더 큰수가 있다면 바로 오큰수로 저장 
  else :
    stack.append(i) # 없다면 일단 스택에 저장, nums의 index를 저장
  while len(stack) and nums[stack[-1]] < nums[i+1] : # 스택이 존재하고 그 다음수가 오큰수일 때 
    nge[stack[-1]] = nums[i+1] # 오큰 수 저장
    stack.pop() # 스택에서 제거

while len(stack) : # 위 반복문을 다 돌고 나서도 스택에 남아있는 숫자들에 대해
  nge[stack[-1]] = -1 # 전부 -1로 오큰수 저장
  stack.pop()
for i in nge :
  print(i,end=' ')
print(-1)