[프로그래머스] 파이썬 _ 수식 최대화 (2020 KAKAO INTERN)

https://programmers.co.kr/learn/courses/30/lessons/67257

코딩테스트 연습 - 수식 최대화

문제유형 : 구현, 리스트?

 

문제풀이 :

• 나는 큐 2개를 이용해서 풀었다.

 

정답코드 : 

# 연산자의 우선순위를 재정의하여 만들수있는 절댓값이 가장 큰 숫자 
# 주어지는 숫자는 모두 양수 
from itertools import permutations
from collections import deque


def solution(expression):
    answer= 0
    # 0. 숫자와 연산자로 분리
    number = ''
    op = set()
    q = deque([])
    for i in expression:
        if i.isdigit():
            number += i
        else:
            q.append(number)
            q.append(i)
            op.add(i)
            number = ''
    q.append(number)

    # 1. 주어진 문자열에 수식이 몇개있는지 확인
    len_op = len(op)
    op = list(op)
    # 2. 수식의 가능한 우선순위를 모두 구한다.
    for case in permutations(op, len_op):

        # 3. 해당 우선순위대로 계산했을때 나온 값들을 이전계산값과 비교하여 더큰값으로 계쏙 저장한다.
        new_q = deque([])
        _q = q.copy() # 새로운 우선순위가 나오면 새롭게 계산해야 하므로 복사해주어야함
        # 3.1. 하나의 연산자마다 전체식을 한번 돌아서 새로운 식을 만든다고 생각
        for i in range(len_op):
            # 큐가 빌때까지
            while _q:
                curr = _q.popleft()
                # 현재 우선순위에 해당하는 연산자라면 
                if curr == case[i]:
                    before = new_q.pop()
                    after = _q.popleft()
                    value = str(eval(before + case[i] + after))
                    new_q.append(value)
                else:
                    new_q.append(curr)
            # 현재 case에 대해 계산이 모두 완료된경우 최대값을 비교하여 갱신 
            if len(new_q) == 1:
                answer = max(answer, abs(int(new_q[-1])))
                break
            _q = new_q.copy()  # 대상이 되는 큐를 새로운 식으로 바꿔준다. 이떄도 꼭 copy를 해줘야함 
            new_q = deque([]) # 위에서 copy를 안하면 이게 반영이됨, 새로운 식을 저장할 공간 초기화 
    print(answer)
    return answer

solution("100-200*300-500+20")

 

기억하자 :

• 파이썬에서 리스트를 다른 변수에 저장할때 레퍼런스가 넘어가서 예상하지 못한 결과가 나올때가 종종 생긴다... 정확히 머리로 설계한뒤에 구현하자.
• 문자열로된 식처럼 숫자+문자가 이어져있는걸 한방에 숫자, 문자 리스트로 쪼개는 방법 - by 정규식
  • ex = re.split(r'(\D)',expression) 
• 더 쉬운 다른분 풀이 

•  연산자의 인덱스를 찾아서 이용!!
  • 현재 우선순위인 연산자를 만나면 해당 인덱스 앞뒤의 값을 가져온후에 연산자 인덱스-1 위치에 해당계산값을 넣어준다.
  • 그후에 연산자인덱스위치, 연산자인덱스+1 위치 값은 없애줘야하므로 리스트 슬라이싱을 이용해 두개값을 없애서 다시 리스트를 이어붙인다.

• def solution(expression):
      #1
      op = [x for x in ['*','+','-'] if x in expression]
      op = [list(y) for y in permutations(op)]
      ex = re.split(r'(\D)',expression)
  
      #2
      a = []
      for x in op:
          _ex = ex[:]
          for y in x:
              while y in _ex:
                  tmp = _ex.index(y)
                  _ex[tmp-1] = str(eval(_ex[tmp-1]+_ex[tmp]+_ex[tmp+1]))
                  _ex = _ex[:tmp]+_ex[tmp+2:]
          a.append(_ex[-1])
  
      #3
      return max(abs(int(x)) for x in a)