수식 최대화

zzwwoonn·2022년 6월 26일
0

Algorithm

목록 보기
63/71

문제

처음엔 조금 해맸는데 계속 손가락을 움직이다 보니? 첫 번째 제출에 바로 정답이 나왔다.

풀이 방법은 간단하다.

  1. 먼저 주어진 문자열에서 연산자만 다 뽑아 낸다.
    => [+, -, +] , 이런 식이다. (set으로 바꿔서 중복제거)
    그럼 사용한 연산자의 종류가 나온 리스트가 될 것이고
  2. 이 리스트로 순열 돌려서 나올 수 있는 우선순위의 모든 경우를 배열로 만들어낸다.
    => 연산자가 3개 다 쓰였으면 6가지가 나올 것이다.
  3. 원래의 문자열을 돌면서 사용된 연산자를 만나면 잘라내는(split) 작업을 한다.
    => [100, +, 200, -, 300, + ~~ ] 와 같은 형태가 될 것이다.
  4. 위에서 만들어 놓은 우선순위 배열을 하나씩 돌면서 작업해야하는 연산자를 찾으면 앞 뒤의 숫자와 함께 계산해준다.

정답 코드

from itertools import permutations

def solution(expression):
    answer = 0

    operList = []
    for a in expression:
        if a == "+" or a == "-" or a =="*":
            operList.append(a)
    operList = set(operList)
    operList = list(permutations(operList, len(operList)))

    # print(operList)
    # [('+', '-', '*'), ('+', '*', '-'), ('-', '+', '*'), ('-', '*', '+'), ('*', '+', '-'), ('*', '-', '+')]

    LL = []
    j = 0
    for i in range(len(expression)):
        # print("i = ", i, " => ", expression[i] )
        
        if expression[i] in operList[0]:
            # input()
            LL.append(expression[j:i])
            LL.append(expression[i])
            j = i+1
            
    LL.append(expression[j:])
    # print(LL) 
    # ['100', '-', '200', '*', '300', '-', '500', '+', 20]

    answer = 0

    for oper in operList:
        # input()
       
        L = []
        for x in (LL):
            L.append(x)
        
        # print("LL = ", LL)
        # print("L = ", L)

        # print("oper = ", oper)
        for operOne in oper:
            # print("operOne = ", operOne)
            while operOne in L:
                # input()

                for i in range(len(L)):
                    if L[i] == operOne:
                        # print("L[i-1] = ", L[i-1])
                        # print("L[i] = ", L[i])
                        # print("L[i+1] = ", L[i+1])

                        strVal = L[i-1] + L[i] + L[i+1]
                        resultInt = eval(strVal)

                        # print(resultInt)

                        L[i-1] = 'X'                    
                        L[i] = str(resultInt)
                        L[i+1] = 'X'

                        while 'X' in L:
                            L.remove('X')

                        # print("L = ", L)
                        break
            if len(L) == 1:
                # print("result Integer = ", L[0])
                break
        answer = max(answer, abs(int(L[0])))
        # print(answer)
    return answer

# 100 , - , 200 , * , 300 , - , 500 , + , 20
# 우선 순위 = * , - , + 이면? 
# 200 * 300 지우고 60000 넣어
# => 100 - 60000 - 500 + 20
# 그 다음 우선 순위 : -
# 100 - 60000 지우고 - ~~ 넣어
# ~~ - 500 지우고 ~~ 넣어




expression = "50*6-3*2"
result = 300
# print(str(result).isalnum())

# expression = "100-200*300-500+20"
# result = 60420

print(solution(expression))
print(result)
# * > + > - 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
# 연산 순서는 아래와 같습니다.
# 100-200*300-500+20
# = 100-(200*300)-500+20
# = 100-60000-(500+20)
# = (100-60000)-520
# = (-59900-520)
# = -60420
# 따라서, 우승 시 받을 수 있는 상금은 |-60420| = 60420 입니다.

깔끔한 코드 (주석 제거)

from itertools import permutations

def solution(expression):
    answer = 0

    operList = []
    for a in expression:
        if a == "+" or a == "-" or a =="*":
            operList.append(a)
    operList = set(operList)
    operList = list(permutations(operList, len(operList)))

    LL = []
    j = 0
    for i in range(len(expression)):
        if expression[i] in operList[0]:
            LL.append(expression[j:i])
            LL.append(expression[i])
            j = i+1
            
    LL.append(expression[j:])
    answer = 0
    for oper in operList:
        L = []
        for x in (LL):
            L.append(x)
        for operOne in oper:
            while operOne in L:
                for i in range(len(L)):
                    if L[i] == operOne:
                        strVal = L[i-1] + L[i] + L[i+1]
                        resultInt = eval(strVal)

                        L[i-1] = 'X'         
                        L[i] = str(resultInt)
                        L[i+1] = 'X'

                        while 'X' in L:
                            L.remove('X')

                        break
            if len(L) == 1:
                break
        answer = max(answer, abs(int(L[0])))
    return answer

0개의 댓글