[Python] 백준 #10799 - 쇠막대기

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

10799번: 쇠막대기

 

 

풀이

arr = list(input())
bar = 0
cnt = 0
i = 0

while True:
    if i==len(arr)-1: break
    if arr[i]=='(':
        if arr[i+1]==')':
            cnt+=bar
            i+=2
            continue
        bar+=1
        cnt+=1
    else:
        bar-=1
    i+=1
print(cnt)

 

 

1. bar(현재 쇠막대기 갯수 (잘리지 않은 것)), cnt(현재 잘린 막대기를 포함한 갯수, 답이 됨) ,i(리스트 참조) 0으로 초기화한다. bar는 레이저로 자르면 생기는 쇠막대기의 갯수라고 보면 편할 것이다.
2. 문자열을 리스트로 만들어준다.
3. 반복문을 돌린다. 이때 arr[i+1]을 참조할것이기 때문에 i==len(arr)-1이면 break
4. 만약 (, ) 이 나오면 레이저가 막대기를 자른다. ()이 나오는 것을 알기위해서는 arr[i]=='(' and arr[i+1]==')'이 True이면된다. 
5. 레이저가 나오면 잘린만큼 cnt에 더해줘야하니 bar만큼 cnt에 더해준다. 이제 레이저의 다음부터 참조해주어야하니 i에 2를 더해주고 continue를 해준다.
6. 만약 레이저가 아니라면[ arr[i+1]!=')' ]  쇠막대기이기때문에 bar를 더해주고 cnt도 더해준다.
7. 만약 arr[i] == ')' 이면 쇠막대기가 끝난것이기 때문에 bar를 -1해준다.

 

만약 처음에 주어진 쇠막대기의  ( , ) 의 짝을 구해야했으면 스택으로 풀었어야겠지만 그런 말이 없어서 그냥 반복문만 돌렸다.