[Algorithm] 3주차 스터디 - 스택

<17608 - 막대기>

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

17608번: 막대기

 

오른쪽에서 바라보았을때 보이는 막대기의 수를 구하는 문제이다. 자신의 오른쪽에 있는 막대기 중 자신보다 높은 막대기가 하나도 없다면 그 막대기는 보일것이다. 즉, 현재 해당 막대기가 자신의 오른쪽에 있는 막대기의 최대값보다 크다면 그 막대기는 보인다. 

따라서 주어진 막대기 높이들을 스택에 넣고 제일 상위에서 부터 (즉, 오른쪽 막대기부터) 하나씩 pop하여 현재 해당 막대기와 현재 까지의 막대기 최대값과 비교하여 해당 막대기값이 더 크다면 개수를 증가시켜준다.

 

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())

bars = deque(int(input()) for _ in range(n))
maxBar = bars.pop()
count = 1

while(bars):
  nowBar = bars.pop()
  if(maxBar < nowBar):
    count += 1
    maxBar = nowBar
    
print(count)

 

---

<10828 - 스택>

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

10828번: 스택

 

스택을 구현하라는 문제이다. 스택은 배열으로도 구현할 수 있고 연결리스트로도 구현할 수 있다. 나는 배열을 이용해서 구현해보았다. 구현해야할 명령은 총 5가지로 push, pop, size, empty, top이다. 각 명령에 따라 처리해주는 부분을 함수로 따로 빼서 정의하여 메인로직을 한눈에 볼 수 있도록 구현하였다.

 

import sys
input = sys.stdin.readline

n = int(input())
stack = list()

def pop():
  if(stack):
    print(stack.pop())
  else:
    print(-1)

def push(num):
  stack.append(num)

def size():
  print(len(stack))

def empty():
  if(stack):
    print(0)
  else:
    print(1)

def top():
  if(stack):
    print(stack[-1])
  else:
    print(-1)

for _ in range(n):
  commandLine = input().split()
  command = commandLine[0]
  if(command == "push"):
    push(int(commandLine[1]))
  elif(command == "pop"):
    pop()
  elif(command == "size"):
    size()
  elif(command == "empty"):
    empty()
  elif(command == "top"):
    top()

 

---

<2504 - 괄호의 값>

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

2504번: 괄호의 값

 

괄호쌍이 주어졌을때 올바른 괄호열일 경우 규칙에 따라 점수를 계산하는 문제이다. 올바른 괄호쌍을 판단하는건 괄호를 차례로 스택에 쌓는다고 했을때 닫는 괄호가 나왔을 경우 스택 최상단에 여는괄호가 나왔는지 확인해주면 되기 때문에 어렵지 않았는데 연산을 하는 부분이 어려웠다.

연산은 "결합법칙"을 통해 풀 수 있다. 예를 들어보겠다.

(()[[]()])
=> 2*(2 + 3*(3 + 2))
=> 2*(2 + 3*3 + 3*2))
=> 2*2 + 2*3*3 + 2*3*2

위 괄호식을 연산으로 나타낸것이다. 이처럼 분배법칙으로 풀어서 나타내보면 특정괄호 안에 있는 괄호식은 해당 괄호값(2 또는 3)이 곱해져 있는것을 확인할 수 있다. 정상적인 문자열이라면 "(" 괄호가 열렸을때 그 사이에 있는것은 X2가 되는것이다. 따라서 temp라는 변수를 두고 만약 "(" 괄호가 열린다면 temp에 2를 곱해주고  ")" 괄호가 닫혔을때 다시 temp를 2로 나눠주는것이다.

그렇다면 언제 result에 temp값을 더해줄까? 바로 (), [] 처럼 바로 이전 괄호와 쌍을 이루는 경우이다. 왜냐하면 (()[]) 처럼 ()안에 또 다른 괄호쌍이 있을 경우는 이미 result에 값이 더해졌기 떄문에 따로 값을 더해줄 필요가 없다. 이를 확인하기 위해 before라는 변수에 바로 이전 괄호가 무엇인지 저장해두었다. 구현방법을 정리하자면 다음과 같다.

 

• temp변수 1로 초기화
• "(", "[" 등 여는괄호일 경우 temp에 괄호값 곱해주고 스택에 PUSH
• ")"일때
  • 스택의 최상단의 괄호가 "("일 경우 스택을 POP해주고 만약 바로 이전 괄호가 "("일 경우 result에 temp값을 더해준다. 괄호가 닫힌것이므로 temp값을 2로 나눠준다.
  • 스택의 최상단의 괄호가 "("가 아닐경우 올바른 괄호쌍이 아니다. 그냥 스택에 PUSH해준다.
• "]"일때는 ")"일 경우와 비슷하므로 생략.

 

해당 괄호들의 for문을 다 돌았을때 올바른 괄호열이라면 짝이 맞아 PUSH가 되기 떄문에 스택이 비어있어야 한다. 따라서 스택이 빈경우에만 result를 출력해주고 아니면 올바르지 않은 괄호열이므로 "0"을 출력한다.

 

import sys
input = sys.stdin.readline
from collections import deque


stack = deque()
brackets = list(input().rstrip())
temp = 1
result = 0
before = ""

for bracket in brackets:
  if(bracket == "("):
    temp *= 2
    stack.append("(")
  elif(bracket == "["):
    temp *= 3
    stack.append("[")
  elif(bracket == ")"):
    if(stack and stack[-1] == "("):
      stack.pop()
      if(before == "("):
        result += temp
      temp = temp // 2
    else:
      stack.append(bracket)
  elif(bracket == "]"):
    if(stack and stack[-1] == "["):
      stack.pop()
      if(before == "["):
        result += temp
      temp = temp //3
    else:
      stack.append(bracket)
  before = bracket
      
      
if(stack):
  print("0")
else:
  print(result)

---

<10773 - 제로>

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

10773번: 제로

 

k개의 정수가 주어질때 이를 차례로 적어 최종 합을 구하는 문제이다.  단, "0"이 나온다면 가장 최근의 수를 지운다. 

k개의 수를 차례로 스택에 넣고 만약 "0"이면 제일 상단의 수를 pop하여 주는 방식으로 구현하였다. k개의 수를 다 돌면 남아있는 스택의 합을 출력해준다.

 

import sys
input = sys.stdin.readline
from collections import deque

stack = deque()

for _ in range(int(input())):
  num = int(input())
  if(num == 0):
    stack.pop()
  else:
    stack.append(num)

print(sum(stack))