[SWEA] #5432 쇠막대기 자르기 평범한 숫자.python(파이썬)

문제 링크 / 출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWVl47b6DGMDFAXm&categoryId=AWVl47b6DGMDFAXm&categoryType=CODE&problemTitle=5432&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

문제요약

쇠막대기와 레이저를 괄호로 나타낸 문자열에서 쇠막대기와 레이저의 위치를 알아내 레이저로 자른 쇠막대기의 조각 수를 구하는 문제.

[제약 사항]

• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다.
• 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.

각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.

• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.

1. 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 “()” 으로 표현된다. 또한, 모든 “()”는 반드시 레이저를 표현한다.
2. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘(’ 로, 오른쪽 끝은 닫힌 괄호 ‘)’ 로 표현된다.

• 괄호 문자의 개수는 최대 100,000이다.

 

풀이

직전의 괄호와 현재괄호가 어떤 조합인지에 따라 4가지 경우로 나누어 풀이했다.

 

1. 직전 : 여는괄호, 현재 : 여는괄호 => 직전의 괄호는 막대의 시작을 의미
2. 직전 : 여는괄호, 현재 : 닫힌괄호 => 레이저를 의미
3. 직전 : 닫힌괄호, 현재 : 여는괄호 => 레이저 / 막대의 끝 이후 레이저 / 막대의 시작이지만 명확하게 알 수 없으므로 다음 괄호가 무엇인지 보고 판단해야함
4. 직전 : 닫힌괄호, 현재 : 닫힌괄호 => 현재의 괄호가 막대의 끝을 의미

 

괄호를 한칸씩 이동하며,

 

• 현재의 위치에서 1번상황이라면 새로운 막대가 시작되므로 막대의 수(bar)를 하나 추가하고, 잘렸을 때 왼쪽부분에 해당하는 조각의 수(cnt)도 하나 추가한다.
• 현재의 위치에서 2번 상황이라면 레이저를 의미, 레이저로 막대를 잘랐을 때 현재까지 위치에서 막대의 수만큼 조각이 증가하므로 cnt에 bar만큼 값을 더해준다.
• 현재의 위치에서 3번 상황이라면 명확하게 알 수 있는 정보가 없으므로 현재 괄호에 대한 정보만 체크한 후 pass.
• 현재의 위치에서 4번 상황이라면 막대의 끝을 의미하므로 막대의 수(bar)를 하나 감소시킨다.

 

최종적으로 조각의 수 cnt를 출력

 

코드

T = int(input())
for tc in range(1, T+1):
    laser_bar = input()
    bar = 0                   # 현재 지점에서 막대기 개수 카운트
    cnt = 0                   # 잘린 조각 개수 카운트
    isleft = False            # 직전의 괄호가 여는 괄호였는지 표시하는 변수

    for lb in laser_bar:
        if lb == '(':
            if isleft:        # 직전의 괄호가 여는 괄호였을 경우 == bar
                cnt += 1      # 레이저로 잘릴때 가장 왼쪽 조각 부분을 추가해줌
                bar += 1      # 새로운 막대기가 시작되므로 막대기 개수 카운트 +1

            isleft = True     # 직전의 괄호가 여는괄호였다는 것을 표시

        else:
            if isleft:        # 여는괄호 직후 닫힌괄호일 때 == laser 
                cnt += bar    # 레이저로 잘린 오른쪽 조각 부분을 추가해줌

            else:
                bar -= 1      # 레이저가 아니라면 쇠막대기를 끝부분이므로 막대기 개수 카운트 -1

            isleft = False    # 직전의 괄호가 여는괄호가 아니었다는 것을 표시

    print('#{} {}'.format(tc, cnt))