문제

' 10779번 쇠막대기 '
https://www.acmicpc.net/problem/10799

Check point

📌 스택 (stack)

💡 스택이란?

• 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조
  => 데이터의 삽익과 삭제가 데이터의 가장 한쪽 끝에서만 일어나는 자료구조

💡 스택 특성

• 선형 구조 : 자료 간의 관계가 1 : 1 ( vs 트리 (비선형 구조 = 1 : N 관계))
• 후입선출 (Last-In-Frist-Out) : 가장 마지막으로 추가된 항목을 가장 첫번째로 제거

💡 스택 연산

• push : 데이터 삽입
• pop : 데이터 삭제 -> pop() : 가장 마지막 데이터 삭제
• top : 가장 마지막에 삽입한 데이터를 삭제하지 않고 return
• isEmpty : 스택이 비어있는지 여부 확인
• peek : 스택의 top에 있는 원소를 반환

📌 문제 조건

• 쇠막대기는 여러개가 겹쳐져 있지만 시작점이나 끝점이 같은 경우는 없고 위에 쇠막대기는 무조건 아래 쇠막대기 보다 짧다.
• 레이저도 쇠막대기 끝점과 겹치지 않는다.
• stack을 써서 저장해 나가는데 시작 점 ( 은 나올 때 마다 레이저인지 확인해 주어야 하고 끝 점 ) 은 나올 때 마다 조각이 잘려진다고 생각한다.

코드

python

lst = input()
total = 0  # 잘려진 조각의 갯수
pre = 0  # 레이저인지 아닌지 판별하기 위해 그 전값과 현재값이 ( ) 인지 확인하기 위해 그 전 값 저장
stack = []
for l in lst:
    if l == '(':
        stack.append(l)
    elif l == ')' and pre == '(':  # 레이저 () 를 만난다면
        stack.pop()  # 레이저 쌍 중 stack에 저장되어 있는 ( 제거
        total += len(stack)  # 겹쳐져 잘려진 쇠막대기 갯수 (stack에 쌓여있는 만큼 추가)
    else:  # 레이저의 끝단과 쇠막대기 오른쪽 끝을 의미하므로 나올때 마다 +1
        stack.pop()  # 해당 쇠막대기는 왼쪽 끝에서 오른쪽 끝까지 다 살폈으므로 제거
        total += 1
    pre = l  # 그 전 값 비교
print(total)

정리 코드

lst = input()
total = 0  
pre = 0  
stack = []
for l in lst:
    if l == '(':
        stack.append(l)
    elif l == ')' and pre == '(':  
        stack.pop()  
        total += len(stack)  
    else: 
        stack.pop()  
        total += 1
    pre = l  
print(total)