서비스기업 알고리즘 기출문제[재귀]

문제 설명

집냥이는 최근 수식에 괄호를 넣으면 결과가 달라질 수 있다는 것을 배웠습니다. 집냥이는 괄호의 기능에 익숙해지기 위해, 정해진 수식에 괄호를 자유롭게 넣어 계산해 나올수 있는 결과를 뽑아보았습니다.

집돌이는 집냥이가 모든 경우의 수에 대해 계산해보았는지 판단하기 위해 하나의 함수를 구현하였습니다. 이 함수는 수식 exp 가 주어졌을 때, 괄호를 자유롭게 넣어 나올 수 있는 모든 결과값을 오름차순으로 정렬하여 반환합니다.

 

예시)

입력 :

exp - "3*2-5*1"

결과:

[-9,-9,- 9,1,11

설명:

(3*(2-(5*1))) . -9

((3*2)-(5*1))= 1

((3*(2-5))*1） = -9

(3x( (2-5)*1)) = -9

(((3x2)-5)*1) = 1

 

제약사항

• 수식의 길이는 20자를 넘지 않습니다.
• 수식의 연산자는 +, -, * 만 사용합니다.
• 수식에 들어있는 숫자는 0 이상 100 미만의 정수입니다.
• 주어진 값을 연산한 결과는 32비트 정수 범위를 넘지 않습니다.

문제 풀이

아래 링크 참고

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

Leetcode 241. Different Ways to Add Parentheses

주의해야 하는 부분

• 100등 연속된 자릿수의 숫자 처리
• 연산자의 위치는 1,3,5,7.....
  • 따라서 길이를 2로 나눈 뒤  2*i+1하면 연산자 위치가 됨
  • 왼쪽과 오른쪽은 나머지 식
    • 해당 식을 연산한 결과를 값으로 치환환 결과를 완전 탐색

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))
def process_list (l):
    if len(l) ==1:
        return l
    res = []
    for i in range(len(1) // 2):
        lod, op, rod = process_list (1[: i*2+1]), 1[i*2+1],process_list(1[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

시간 복잡도는 근사적으로 N!(N=연산자의 갯수)가 되지 않을까 싶다.