[백준][문제 풀기] 알고리즘 기초 1/2 - 10799 쇠막대기

이번 문제는 정답비율이 63퍼 정도 되는 문제다.
바로 풀이과정을 보자

---

import sys

if __name__ == "__main__" :

    # 데이터를 잘 받자!
    str_ = sys.stdin.readline().strip()

    staack = []
    sticks = {}
    total_frags = 0

    its_laser = False

    for i, v in enumerate(str_) :
        if i < len(str_)-1 and (v+str_[i+1]) == "()" :
            # 레이저
            for v in sticks :
                sticks[v] += 1
            its_laser = True
            continue
        elif its_laser :
            its_laser = False
            continue
        elif v == "(" :
            staack.append(1)
            if len(staack)-1 not in sticks :
                sticks[len(staack)-1] = 0
        elif v == ")" :
            lastone = len(staack)-1
            # 닫힌 스틱이 포함하는 laser 수 + 1이 곧 조각 수
            total_frags += (sticks[lastone] + 1)
            del sticks[lastone]
            staack.pop()

    print(total_frags)

시간초과

• 위 풀이에서 시간초과가 났다. 제한시간이 1초여서 상당히 느슨할거라 생각했는데, 전혀 그렇지 않았다.
• 스택구조로 변경하고 코딩의 편의를 위해 dictionary를 사용한 것을 없애야할거같다.

import sys

if __name__ == "__main__" :

    # 데이터를 잘 받자!
    str_ = sys.stdin.readline().strip()

    sticks = []
    total_frags = 0


    for i, v in enumerate(str_) :
        if v == "(" :
            sticks.append(0)
        elif v == ")" :
            if i > 0 and str_[i-1] == "(" :
                # 레이저
                for i, v in enumerate(sticks) :
                    sticks[i] += 1
                continue
            lastone = len(sticks)-1
            # 닫힌 스틱이 포함하는 laser 수 + 1이 곧 조각 수
            total_frags += (sticks.pop() + 1)

    print(total_frags)

시간초과

• stack 구조로 가서 시간 소모를 줄였다 생각했는데, 중간 for문 때문에 여전히 시간초과가 나는 모양이었다.

import sys

if __name__ == "__main__" :

    # 데이터를 잘 받자!
    str_ = sys.stdin.readline().strip()

    sticks = []
    total_frags = 0

    for i, v in enumerate(str_) :
        if v == "(" :
            sticks.append(len(sticks)+1)
        elif v == ")" :
            if str_[i-1] == "(" :
                # 레이저
                sticks.pop()
                if len(sticks) > 0 :
                    total_frags += sticks[-1]
            else :
                # 나머지 조각 수
                total_frags += 1
                sticks.pop()

    print(total_frags)

정답 맞춘 풀이

• stack을 할 때 미리 현재의 stack 사이즈를 push하면 간단히 해결이 된다.
• 그런데 이렇게 진행 할거면 차라리 stack을 하는게 아니라 그냥 stack size만 변수로 저장해도 될 것 같다.
• 이 문제의 핵심은 stack 구조를 이해하고, 적절히 효율적인 코드로 만들 수 있느냐인것같다. 더 빨리 풀어야할텐데 갈 길이 멀다