[백준] 10799번 쇠막대기 - Python(파이썬)

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

10799번: 쇠막대기

 

문제

 

접근법

 

total은 현재 총 쇠막대기 개수 - '('일 때 새로 추가되는 개수를 더해주어야 함.

cnt는 현재 잘리기 전 큰 쇠막대기 개수

i는 현재 괄호 위치

1. '('가 추가될 때는, total과 cnt에 1더하기
2. ')'가 추가될 때는, cnt에 1 빼기
3. '('과 ')'가 연속으로 나올 때는, total과 cnt를 더하고 i 하나 건너 뛰어주기

 

코드

s=input()
total=0
cnt=0
i=0
while i<len(s):
    if s[i]=='(' and s[i+1]==')':
        total=total+cnt
        i+=1
    elif s[i]=='(':
        total+=1
        cnt+=1
    elif s[i]==')':
        cnt-=1
    i+=1

print(total)

 

21.07.23 접근법

1. 막대기 갯수 규칙 찾기
각 막대기의 개수를 구하는 규칙을 찾아보니 "나눈갯수*2-(나눈갯수-1)"를 도출
그럼 이제, 쇠막대기가 몇개인지 찾고, 각 막대기가 나눠진 갯수를 찾아야 함.

stick_cnt : 현재 막대기 개수 측정 변수 
list(sticks) : 막대기들 나눠진 갯수 카운팅하는 모음 변수 (sticks의 인덱스들이 막대기 각 하나를 의미)


2. 쇠막대기 파악
'(' 나오면 stick_cnt 증가
')' 나오면 sticks 마지막 인덱스에 있는 값을 막대기갯수규칙 적용 후 제거
stick_cnt 감소

 

3. 나눠진 갯수 파악

'()' 나오면 막대기 존재 갯수만큼 sticks 인덱스들 1씩 증가

 

로 했지만, 시간 초과

list를 deque로 바꿔도 마찬가지

stick_cnt=0
sticks=[]
ans=0
i=0
line=input()

while i<len(line):
    if line[i]=='(' and line[i+1]==')':
        for j in range(stick_cnt):
            sticks[j]+=1

        i+=1
        
    elif line[i]=='(':
        sticks.append(0)
        stick_cnt+=1

    elif line[i]==')':
        end=sticks.pop()
        ans+=end*2-(end-1)
        stick_cnt-=1

    i+=1

print(ans)

 

때문에 2월에 한 코드 참조 후, 그 때를 상기시켜 하게 됨.

 

total은 현재 총 쇠막대기 개수 - '('일 때 새로 추가되는 개수를 더해주어야 함.

cnt는 현재 잘리기 전 큰 쇠막대기 개수

i는 현재 괄호 위치

1. '('가 추가될 때는, total과 cnt에 1더하기
2. ')'가 추가될 때는, cnt에 1 빼기
3. '('과 ')'가 연속으로 나올 때는, total과 cnt를 더하고 i 하나 건너 뛰어주기

21.07.23 코드

s=input()
total=0
cnt=0
i=0
while i<len(s):
    if s[i]=='(' and s[i+1]==')':
        total=total+cnt
        i+=1
    elif s[i]=='(':
        total+=1
        cnt+=1
    elif s[i]==')':
        cnt-=1
    i+=1

print(total)