[알고리즘 연습] 괄호의 점수

괄호의 점수

• (,)의 두개의 문자로만 구성된 올바른 괄호문자열이 입력으로 주어진다. (짝이 안맞는 경우는 없음)
• “()” 은 1점
• '('과 ')' 사이에 n점짜리 문자열이 있다면 (2*n)점으로 계산
• 둘 이상의 괄호가 나란히 있다면 두 괄호의 점수를 합침
• ex. "(()(()()))" 는 10점

---

풀이

def getParenthesisScore(st):
    Fragments = []
    # ')'과 '('이 만나는 지점을 기준으로 나눠 각각을 'Fragment'라 부름
    # Fragments는 이들 Fragment들이 담기는 공간
    # 예를 들어  ()()(())는 () / () / (())로 나누어져 Fragments에 저장된다.
      
    Fragment = ""
    # Fragment가 저장될 공간. () or (()) or ((())) or ...
    # Fragments에 현재 축적된 정보(Fragment)를 저장하고 Fragment 리스트는 초기화함.

    n = 0
    # '('가 나오면 +1 
    # ')'가 나오면 -1할 변수이다. 
    # ')'가 나와 -1했는데 0이 되었다는 것은 괄호가 닫혔다는 뜻

    for c in st:
        if c == '(':
            n += 1
            Fragment += c
        elif c == ')':
            n -= 1
            Fragment += c
            if (n == 0):
                # 0이 되어었다는 뜻은 괄호가 닫혔다는 뜻이므로 현재 Fragment를 Fragments에 담고, 
                Fragments.append(Fragment)
                # 다음 Fragment를 담을 수 있도록 Fragment를 초기화한다.
                Fragment = ""
    
    score = 0
    # 현재 정보 스코어화
    # Fragments를 돌면서 각각의 점수를 체크할 것
    for Fragment in Fragments:
        # 기본 형태인 '()'는 무조건 1점
        if Fragment == "()":
            score += 1
        # 나머지는 *2, 단 그 내부에는 어떤 형태가 있을지 모르므로 재귀를 활용한다.
        # 괄호 한 껍데기만 벗기고 재귀진행
        # ex. '(())' 에서 '()'만 새로 재귀진행 단 해당 리턴값에 *2를 해서 score에 더해줌 
        else:
            score += getParenthesisScore(Fragment[1:-1])*2
    return score

def main():
    examples = ["()()(())", "(()(()))", "((()())())", "()", "((()))()"] 
    # 4, 6, 10, 1, 5 점이 나와야 합니다.
    for example in examples:
        print(example, getParenthesisScore(example))

if __name__ == "__main__":
    main()

• 재귀로 풀어야한다는 직감은 들었다. 괄호 속 괄호가 몇개나 존재할지 알 수없기 때문이다.
• ')'과 '('만나는 것을 기준으로 나누고, 이를 나눠서 처리하도록 했다.
• 리턴조건을 "()"로 하고 그렇지 않을 경우 제일 왼쪽과 제일 오른쪽의 '('와 ')'쌍을 제거한뒤 *2하고 재귀문을 돌도록 한다.
• 문제는 해결했지만 코드가 지저분해서 찝찝한 느낌. 아직 재귀에 익숙하지 않은 것 같다.
• 더 좋은 풀이가 있다면 공유 바랍니다.ㅠ