[ BOJ / 파이썬 ] 10799 쇠막대기

 

/  제출  1  /

 

이 문제가 스택을 활용하는 유형이라는 것을 알면 그래도 접근하는 난이도가 확 낮아진다. 그래서 그 부분을 눈치 챌 수 있어야겠다. 보통 이렇게 나열식이고 짝 맞춰서 뭔가가 이뤄지는 건 스택일 확률이 높다.(백퍼센트 아니닌까 혹시나헤매지 말것. 확률이 높긴 하니까 의심의 실마리 정도)

 

import sys
input = sys.stdin.readline


brackets = input()

stack = []
result = 0
for b in brackets:
  if not stack:
    stack.append(b)
    continue

  if b == '(':
    stack.append('(')

  if b == ')':
    if stack[-1] == '(':
      stack.pop()
      stack.append(1)
    else:
      k = 0
      while stack[-1] != '(':
        k += stack.pop()
      stack.pop()
      result += k + 1
      stack.append(k)
print(result)

 

로직을 생각하는게 까다로운 문제였다. 레이저일 때, 끝과 끝이 완성됐을 때 두 가지 케이스를 나누고 각각 케이스에서 어떤 동작을 해줄 지를 떠올려야 했다.

레이저뿐일 때는 1개 값을 일단 넣고,

끝과 끝이 만나지면 모인 레이저만큼 갈라준다고 생각해 레이저 값 + 1을 그 막대의 길이로 생각해서 결과값에 더한다.

이 때 겹쳐졌는데 아직 안 끝난 막대를 위해 모인 레이저는 다시 넣어줬다.

 

다시 넣어주는 과정에서 내 착각으로 중복이 생겼는데,

 

풀면서 오류 파트

 

결과값에만 1을 더해줘야 하는데, K값 자체에 1을 더해서 그 다음 막대를 계산할 때는 허수의 레이저값이 추가되었다.

 

그래서 해당부분을 

고친 파트

위의 사진과 같이 고쳤다.

 

 

아무리 생각해도 나는 지금 실버 3-1정도 레벨인 듯.. 딱 요정도 문제들이 30분 내로 풀린다..

한 달(도 아니고 2-3주) 내로 골드 3-1까지 어떻게든 끌어올려야 한다.