Leetcode 241: Different Ways to Add Parentheses(수식 모든 경우의 수 계산하기)[BFS,DFS]

원문 : https://blog.devgenius.io/leetcode-241-different-ways-to-add-parentheses-e2612dd8e86f

Leetcode 241. Different Ways to Add Parentheses

BFS, DFS 패턴은 거의 다 마스터 했다고 생각했는데, 이러한 토크나이징 문제에 약점이 있었을 줄은 몰랐다.

1*1-2+3*4의는 연산자가 3개이기 때문에 총 3! === 6개의 결과가 나온다.

즉 중복을 허용하는 순열이다.

또한 연산 순서에 따라 왼쪽 오른쪽의 결과가 달라지기 때문에 매번 새로 계산해야 한다.

즉 완전 탐색 문제이며 DP를 적용하기 어렵다.

그리고 또 주의할 점은 1000과 같이 연속된 숫자가 있는 경우 처리이다.

 

연산자를 만났을 때, isEndofElem 플래그를 True로 체크해주고,

False가 2번 연속 나온다는 것은 숫자가 2개 연속되었다는 것임으로 이전 값에 10을 곱해 누적해준다.

def solution(exp):
    split_list= []
    isEndOfElem = True
    for ch in exp:
        if ch.isdigit() and isEndOfElem:
            split_list.append(int (ch))
            isEndOfElem = False
            continue
        if ch.isdigit() and not isEndOfElem:
            split_list[-1] = (split_list[-1] * 10) + int(ch)
            continue 
        split_list.append(ch)
        isEnd0fElem = True
    return sorted(process_list(split_list))

처리된 결과 리스트의 홀수 위치에는 항상 연산자가 존재하게 된다.

따라서 길이의 //2를 한 i 인덱스에 i*2+1을 한 위치에는 항상 연산자가 존재한다.

그 앞 뒤로 짤라서 재귀 호출 후 결과값을 만들면 된다.

[1,+,3,+.5]의 경우 맨 처음에 [1] + [3,+,5] 두 개로 나누어지고

그 다음에 [1] + [8]이 되어 res에 [9]가 들어간다.

그 다음 [1,+,3] + [5]가 처리될 것이다.

따라서 결과는 [9,4]가 된다.

 

원문에서는 다음과 같은 그림으로 설명한다.

위 풀이를 설명한 그림

def process_list (l):
    if len(l) ==1:
        return l
    res = []
    for i in range(len(l) // 2):
        lod, op, rod = process_list (l[: i*2+1]), l[i*2+1],process_list(l[i*2+2:])
        for outl in lod:
            for outr in rod:
                if op == "+":
                    res. append (outl + outr)
                if op =="-":
                    res. append (outl - outr)
                if op =="*":
                    res.append (outl * outr)
                return res