백준-10799

쇠막대기
04.18에 푼 문제입니다🌷

  1. 막대기를 구현해서 하나씩 자르는 수를 고려함.
import sys
input=sys.stdin.readline

line=list(input())
cut=False
result=0
#각 쇠 막대기마다 몇 번 잘리는 지 쇠막대기의 잘리는 횟수를 stack에 저장
stack=[]

for i in line:
  if i == '(':
    cut=True
    #새로운 쇠 막대기 시작
    stack.append(0)
  elif i == ')':
    #() 자르는 괄호가 끝났을 때
    if cut==True:
      stack.pop()
      for j in range(len(stack)):
        stack[j]+=1
    # 쇠 막대기가 끝났을 때
    elif cut==False:
      result+=stack.pop()+1
    cut=False
  
print(result)

결과는 잘 나오는데 시간초과가 발생한다. 두번째 for 문 때문인거 같다.

  1. 레이저가 쐈을 때 막대가 추가되는 것으로 구현
import sys
input=sys.stdin.readline

line=list(input())
cut=False
result=0
#각 쇠 막대기마다 몇 번 잘리는 지 쇠막대기의 잘리는 횟수를 stack에 저장
stack=[]

for i in line:
  if i == '(':
    cut=True
    stack.append(i)
    #새로운 막대가 추가될때 result에 막대 하나 추가
    result+=1
  elif i == ')':
    stack.pop()
    #쇠 막대기가 아니라 레이져일 때
    if cut==True:
      #레이져이므로 result에서 막대 개수를 빼준다
      result-=1
      #레이져로 자를때 막대기가 있는 만큼 생기므로 result에 더해준다
      result+=len(stack)
    cut=False

  
print(result)

통과~~~✌️🐰🐰🐰

좋은 웹페이지 즐겨찾기