[문제] 쇠막대기

시간초과 때문에 90점짜리 풀이..테스트 17 18을 통과하지 못했다.

import re

def solution(arrangement):
    answer = 0
    
    # print(arrangement)
    
    # 각 레이저를 감싸고 있는 괄호의 갯수 * 2 를 하면 된다!
    
    # 문제는 감싸고 있는 괄호의 갯수를 어떻게 셀 것인가?
    
    # 각 방향과 같은 모양의 괄호 갯수를 세고 거기에서 다른 모양을 빼주면 됨!
    
    # 먼저 레이저를 찾자..
    lasers = [x.start() for x in re.finditer('\(\)',arrangement)]
    # print(lasers)
    
    l = len(lasers)
    
    # 각각의 레이저에 대하여 오른쪽을 기준으로 자신을 감싸고 있는 괄호들이 몇개인지 찾자
    for i in lasers: # i 가 인덱스다!
        paren = 0
        paren += arrangement[i+2:].count(')')
        paren -= arrangement[i+2:].count('(')
        
        answer += paren
    else:
        # 원래 토막의 갯수 더해줌
        # 레이저 빼고 한방향의 paren 갯수만 세어주면 됨
        # tomak = arrangement.replace('()','')
        # print(tomak)
        
        answer += arrangement.count('(') - l
    return answer

절대 뒷부분의 테스트케이스를 통과할 수 없었기 때문에 다른 풀이로 접근해본다.

def solution(arrangement):
    answer = 0

    arrangement = arrangement.replace('()','l')

    print(arrangement)

    # 각각의 레이저를 기준으로 감싸고 있는 괄호의 갯수 (쇠막대의 수) 를 세고 그만큼씩 더해준다.
    for i,v in enumerate(arrangement):
        if v == 'l':
            makdae = 0
            makdae += arrangement[i+1:].count(')')
            makdae -= arrangement[i+1:].count('(')
            answer += makdae
    else:
        # 마지막으로 원래 막대의 갯수를 더해준다
        answer += arrangement.count('(')

    return answer

접근방식은 같지만 처음에 그냥 레이저들을 'l'로 바꿔줘버렸다. 통과했다.

다른 풀이를 보자!

def solution(arrangement):
    answer = 0
    sticks = 0
    rasor_to_zero = arrangement.replace('()','0')
    
    print(rasor_to_zero)

    for i in rasor_to_zero:
        if i == '(':
            sticks += 1
        elif i =='0' : 
            answer += sticks
        else :
            sticks -= 1
            answer += 1

    return answer

효율성에서 내 풀이는 쨉도안된다. 슬프다. 어떻게 이런 생각을 하지?
일단 for문을 최대한 덜써야 한다. 제일 적은 순회가 답이라는 생각을 해야한다.
한바퀴 돌면서 모든 일들을 해낼 수 있으려면 어떻게 해야할까? 라는 생각을 했어야한다. 3가지 경우다. (, 레이저, ) . 각각의 경우에 어떤 처리를 하면 한번에 원하는 결과를 얻어낼 수 있으리라는 생각을 했어야한다.