[CodingTest] BOJ10799 쇠막대기 ( 자료구조 ) With 파이썬

10799번: 쇠막대기

 

 

◎ 문제풀이

 

문제에 제시된 단어 하나하나를 모두 자료구조로 만들 필요는 없다. (완벽주의 조심!) 문제의 목적에 달성하기 위한 수단만 필요할 뿐이다. 즉, 레이저, 막대가 나왔다고 레이저, 막대를 자료구조로 만들 필요가 없다는 의미이다. 

 

레이저가 막대기를 자르면 막대의 개수는 레이저 개수 + 1개 이다.

"()"가 레이저이므로 레이저가 나올때까지 막대를 기억해야 한다고 생각해서 STACK을 떠올렸다. 

 

")"는 두가지 경우가 있다.

 

1. 레이저인 경우

레이저가 등장하면 STACK에 저장된 막대기는 모두 잘린다. 

 

총 잘려진 막대개수 += STACK에 저장된 막대개수

 

2. 막대인 경우

 

총 잘려진 막대개수 += 1 

막대기는 레이저개수 +1개로 잘린다. 지금까지 레이저가 나올때 마다 잘려진 막대개수에 추가되었으니 마지막으로 +1을 해주어야 한다. 

 

 

◎ 코드

import sys
input = sys.stdin.readline

items = list(input().rstrip())
stack = []
stack.append(items[0])

block_count = 0

for i in range(1,len(items)) :
  if items[i] == "(" :
    stack.append(items[i])

  elif items[i] == ")" :
    if items[i-1] == "(" : 
      stack.pop()
      block_count += len(stack) 
    else :
      stack.pop()
      block_count += 1

print(block_count)