Python의 서투른 팩토리얼

<시간/>

양의 정수 n의 계승은 n보다 작거나 같은 모든 양의 정수의 곱이라는 것을 알고 있습니다. 따라서 factorial(10) =10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1입니다. 우리는 서투른 계승을 찾으려고 노력할 것입니다. 정수를 내림차순으로 사용하여 연산의 고정 회전:곱하기(*), 나누기(/), 더하기(+), 빼기(-) 순서로.

clumsy 계승은 clumsy(10) =10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1과 같습니다. 그러나 이러한 연산은 여전히 일반적인 산술 연산 순서를 사용하여 적용됩니다. 모든 곱셈을 수행합니다. 및 덧셈 또는 뺄셈 단계 이전의 나눗셈 단계, 곱셈 및 나눗셈 단계는 왼쪽에서 오른쪽으로 처리됩니다. 우리가 사용하는 나눗셈은 10 * 9 / 8이 11이 되는 바닥 나눗셈입니다. 이것은 결과가 정수임을 보장합니다.

예를 들어, 입력이 10이면 결과는 12가 됩니다. 12 =10 * 9 / 8 + 7 – 6 * 5 / 4 + 3 – 2 * 1

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

opeartions 배열을 정의하고 연산자 [* / + -]를 저장하고 하나의 빈 스택을 만들고 N을 스택에 넣습니다.
색인:=0
N을 1 감소
N이 0이 아닌 동안:
- 만약 작업[인덱스] =*, then
  - 스택 상단 요소가>=0이면 스택 상단 요소를 top_element :=N * top_element로 업데이트합니다.
  - 그렇지 않으면 스택 상단 요소 :=-1 * |N * 스택 상단 요소|
- 만약 작업[색인]이 /이면
  - 스택 상단 요소가>=0이면 스택 상단 요소를 top_element :=top_element / N으로 업데이트
  - 그렇지 않으면 스택 상단 요소 :=-1 * |스택 상단 요소 / N|
- else [index] 연산이 +이면
  - 스택에 N 삽입
- else 삽입(-1 * N)을 스택에
- index :=(index + 1) 연산 배열의 모드 길이
- N을 1 감소
스택 요소의 합계를 반환합니다.

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution(object):
   def clumsy(self, N):
      operations = ["*","/","+","-"]
      stack = []
      index = 0
      stack.append(N)
      N-=1
      while N:
         if operations[index] == "*":
            if stack[-1]>=0:
               stack[-1] *=N
            else:
               stack[-1] = -1*(abs(stack[-1])*N)
         elif operations[index] == "/":
            if stack[-1]>=0:
               stack[-1] //=N
            else:
               stack[-1] = -1*(abs(stack[-1])//N)
         elif operations[index] == "+":
            stack.append(N)
         else:
            stack.append(-1*N)
         index = (index+1) % len(operations)
         N-=1
      return sum(stack)
ob = Solution()
print(ob.clumsy(10))

Python의 서투른 팩토리얼

예시

입력

출력