(D4)5432_쇠막대기자르기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWVl47b6DGMDFAXm&categoryId=AWVl47b6DGMDFAXm&categoryType=CODE&problemTitle=%EC%87%A0%EB%A7%89%EB%8C%80%EA%B8%B0&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

실패로 끝난 첫번째 아이디어

• 각각 괄호 안에 ()가 몇개 들어있는지 센다음 그것을 합산해주면 되겠다!

제한시간 초과로 실패

import sys
sys.stdin = open("input.txt")

T = int(input())
# 제한 시간 초과

for tc in range(1, T+1):
    inp = input()
    L = len(inp)

    cnt_close = 0 # () 괄호가 닫혔는지 체크
    cnt = 0 # 안에 () 가 몇개 들었는지 체크
    result = 0 # 결과

    for i in range(L) :
        cnt = 0
        cnt_close = 0
        if inp[i] == "(" :
            cnt_close +=1
            for j in range(i+1, L) : # 그 다음부터 끝까지 확인 - 괄호 닫히는 거 체크
                if inp[j] == "(" :
                    cnt_close +=1
                    if j < L-1 and inp[j+1] == ")" : # () 괄호 갯수세기
                        cnt+=1
                else :
                    cnt_close -=1
                    if cnt_close == 0 :
                        result += cnt+1 if cnt!=0 else 0 # cnt 가 0이 아니면 cnt+1 로 더해지고, 아니면 0
                        break


    print("#{} {}".format(tc, result))

두번째 도전

• 아이디어

  • (를 만나면 cnt +=1

    )를 만나면 cnt-=1 을 해줘서 cnt로 누적된 판의 갯수를 구하자

  • )를 만날때 반응이 두가지 경우

    • (가 바로 앞에 있었을 경우 - 레이저로 자른다
    • )가 바로 앞에 있을 경우 - 잘리고 남은 자투리 하나를 계산

import sys
sys.stdin = open("input.txt")

T = int(input())


for tc in range(1, T+1):
    inp = input()

    cnt = 0
    result =0
    back=")"
    for tmp in inp :
        if tmp == "(" :
            cnt+=1
        else :
            cnt -= 1
            if back=="(" :
                result += cnt  # 잘리는 판의 갯수
            else :
                result+=1 # 판이 끝날때 남는 조각 1개

        back=tmp #이전꺼

    print("#{} {}".format(tc, result))

스택으로 구현

• 두번째 시도한 내용과 똑같으나, 스택을 활용해서 좀더 직관적으로 판의 누적을 표현할 수 있다.

import sys
sys.stdin = open("input.txt")

T = int(input())

# 스택을 이용한 풀이
for tc in range(1, T+1):
    inp = input()
    stack = []
    result = 0
    back = 0

    for tmp in inp :
        if tmp == "(" :
            stack.append(tmp)
        else :
            stack.pop()
            if back != tmp :
                result += len(stack) # 쌓여있는 판 갯수
            else :
                result +=1

        back = tmp
    print("#{} {}".format(tc, result))