[알고리즘] 크래프톤 정글 1주차 / 알고리즘 中 혼자서 못 푼 문제 정리1(괄호의 값)

BOJ 2504 괄호의 값

난이도 : (크래프톤 정글 기준) 상, (백준 난이도 기준) 골5

사용 알고리즘 or 자료 구조 : 스택

 

처음 생각한 풀이

처음 문제를 풀기 전에 주제를 봤을 때나, 지문을 읽었을 때나 '아, 스택을 사용해야되네.'라고 생각했었다.

문제는 어떻게 구현할지 감이 잡히지 않았던 것이다.

 

프로그래머스에서 올바른 괄호식 형태인지를 판단하는 문제를 풀어봤기에 이 문제도 비슷할 것이라 생각했지만, 이 문제는 올바른 괄호식 형태인지 판단 + 괄호식으로 숫자 계산을 시켜서 프로그래머스의 문제보다 어려웠다.

(프로그래머스 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12909)

 

처음 생각했던 방법은 스택으로 감이 잡히지 않아 재귀함수를 사용하는 방법이었다.

 

'(' 나 '[' 를 만나면 다음과 같이 재귀함수를 호출하여(return 2 * dfs(다음 인덱스) 혹은 return 3 * dfs(다음 인덱스)) 곱셈과 덧셈을 분리할 생각이었다.

 

하지만 생각을 해보니 괄호가 닫히고 새로운 괄호가 열렸을 때 대응하는 조건이나, 제대로 되지 않은 괄호식일 때 0을 return할 방법이 없어서 이 방법을 바로 폐기했다.

구글링 이후 풀이

아무리 생각해도 답이 떠오르지 않아해서 접근법을 구글에 찾아보았다.

 

접근법은 괄호를 stack에 담아 올바른 괄호식인지 판단하면서 분배 법칙을 활용하면서 수식을 계산해주는 것이었다.

예를 들어, ( ( ) [ [ ] ] ) 이라는 괄호식이 있다고 하자. 이 괄호식을 규칙대로 계산하면 2 * (2 + 3 * 3)이 되어 22가 나온다.

분배 법칙을 적용하여 식을 정리해주면 (2 * 2) + (2 * 3 * 3) 이 된다.

 

이 것만 보고 문제에 어떻게 적용하는지 전혀 감이 안 올 것이다. 풀이법을 함께 보도록 하자.

 

먼저 계산을 시작해줄 num = 1로 초기화를 시킨 다음 입력 받은 string을 앞에서부터 보는 것으로 시작한다.(반복문 시작 전 계산된 num을 더해줄 sum을 0으로 초기화 해야한다.)

string을 차례차례 보며 이번 차례의 string의 문자에 따라 어떻게 하는지 아래에 적도록 하겠다.

 

- 이번 문자가 ' ( ' 인 경우

    num에 2를 곱한 뒤 stack에 ' ( ' 를 push 한다.

- 이번 문자가 '[ ' 인 경우

    위와 같이 num에 3을 곱한 뒤 stack에 ' [ ' 를 push 한다.

- 이번 문자가 ' ) ' 인 경우

   1) stack이 비어있는 상태거나 스택의 top에 위치한 문자가 ' ( ' 가 아닌 경우 :

          sum을 0으로 바꾸고 반복문 탈출

   2) 이전 차례의 문자(string[i-1])가 ' ( '인 경우 :

          sum에 num을 바로 더해준다.

   위의 경우를 다 처리했다면 괄호 안에 있는 식에 2를 곱해주는 과정이 끝난 것이므로 num을 2로 나눠주고,

   stack에서 pop을 해주도록 하자.

- 이번 문자가 ' ] ' 인 경우

   위의 경우와 비슷하므로 이건 스스로 해주도록 하자.

 

이런 식으로 모든 순회가 다 끝나고 난 뒤, 정상적인 괄호식이라면 stack의 크기가 0이 될 것이다.

따라서 stack의 크기가 0일 때만 sum을 출력하고 아니면 0을 출력해주도록 하자.

 

 

 

 

 

 

※ 스 포 주 의 ※

 

 

 

 

코드

import sys

N = sys.stdin.readline()

st = []

sum = 0

num = 1

# 분배법칙을 이용

# EX : (()[[]])

# 계산 : 2x(2+3x3)=22

# 분배법칙을 보면 (2x2) + (2x3x3) 로 계산됨

for i in range(len(N) - 1):

    if N[i] =='(':

        # ( 가 오면 현재 계산중인 num에 2를 곱해줌

        num *= 2

        st.append(N[i])

    elif N[i] == '[':

        # [ 가 오면 현재 계산중인 num에 2를 곱해줌

        num *= 3

        st.append(N[i])        

    elif N[i] == ')':

        # ) 가 오면

        if len(st) == 0 or st[-1] != '(':

            # 스택이 비어있거나 스택의 최근 문자가 ( 가 아니면 괄호 오류이므로 sum = 0으로 만들고 반복문 탈출

            sum = 0

            break

        if N[i - 1] == '(':

            # 이전 차례의 문자가 ( 라면 곱셈을 닫는 것이므로 sum에 num을 더한 뒤, 2로 나눠줌

            sum += num

        num //= 2

        st.pop()

    else: # N[i] == ']'

        # ) 가 오면

        if len(st) == 0 or st[-1] != '[':

            # 스택이 비어있거나 스택의 최근 문자가 [ 가 아니면 괄호 오류이므로 sum = 0으로 만들고 반복문 탈출

            sum = 0

            break

        if N[i - 1] == '[':

            # 이전 차례의 문자가 [ 라면 곱셈을 닫는 것이므로 sum에 num을 더한 뒤, 3으로 나눠줌

            sum += num

        num //= 3

        st.pop()

# 제대로 된 괄호인지 확인

if len(st) == 0:

    print(sum)

else:

    print(0)