Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 풀어보는 서툰 팩토리얼(Clumsy Factorial) 알고리즘

서툰 팩토리얼이란?

양의 정수 n의 팩토리얼(factorial)은 n 이하의 모든 양의 정수를 곱한 값입니다. 예를 들어 factorial(10) = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1과 같습니다.

이번 글에서는 일반적인 팩토리얼이 아닌 '서툰 팩토리얼(clumsy factorial)'을 구해 보겠습니다. 서툰 팩토리얼은 정수를 내림차순으로 사용하되, 곱셈 연산을 곱하기(*), 나누기(/), 더하기(+), 빼기(-)라는 고정된 순서로 순환하는 연산들로 교체하는 방식입니다.

예를 들어 clumsy(10)은 다음과 같이 계산됩니다.

clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

다만 이 연산들은 여전히 일반적인 산술 연산의 우선순위 규칙을 따릅니다. 즉, 모든 곱셈과 나눗셈을 먼저 수행한 뒤 덧셈과 뺄셈을 처리하며, 곱셈과 나눗셈끼리는 왼쪽에서 오른쪽 순서로 계산합니다. 또한 나눗셈은 바닥 나눗셈(floor division)을 사용하기 때문에 10 * 9 / 8은 11이 되고, 이를 통해 계산 결과가 항상 정수임을 보장할 수 있습니다.

따라서 입력값이 10이라면 최종 결과는 다음과 같이 12가 됩니다.

12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

문제 해결 접근 방법

이 문제는 스택(stack) 자료구조를 활용하면 깔끔하게 해결할 수 있습니다. 연산 우선순위를 직접 관리하지 않아도, 곱셈과 나눗셈은 스택의 최상단 값을 갱신하고 덧셈과 뺄셈은 새 요소를 push하는 방식으로 처리할 수 있습니다.

알고리즘 단계

  • 연산자 배열 [*, /, +, -]를 정의하고, 빈 스택을 하나 생성한 뒤 N을 스택에 push합니다.
  • index := 0으로 초기화합니다.
  • N을 1 감소시킵니다.
  • N이 0이 아닌 동안 다음을 반복합니다:
    • operations[index]가 '*'이면:
      • 스택 최상단 요소가 0 이상이면 top_element := N * top_element로 갱신
      • 그렇지 않으면 stack_top := -1 * |N * stack_top|로 갱신
    • operations[index]가 '/'이면:
      • 스택 최상단 요소가 0 이상이면 top_element := top_element // N으로 갱신
      • 그렇지 않으면 stack_top := -1 * |stack_top // N|으로 갱신
    • operations[index]가 '+'이면 N을 스택에 삽입합니다.
    • 그 외('-')의 경우 -1 * N을 스택에 삽입합니다.
    • index := (index + 1) mod len(operations)로 갱신합니다.
    • N을 1 감소시킵니다.
  • 스택에 남아 있는 모든 요소의 합을 반환합니다.

곱셈과 나눗셈 단계에서 부호를 별도로 처리하는 이유는, 파이썬의 정수 나눗셈(//)이 음수에 대해서는 바닥(floor) 방향으로 작동하기 때문입니다. 절댓값을 기준으로 계산한 뒤 부호를 붙여 주면 의도한 바닥 나눗셈 결과를 정확히 얻을 수 있습니다.

파이썬 구현 예제

아래 코드를 통해 실제 구현 과정을 더 쉽게 이해할 수 있습니다.

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))

실행 결과 확인

입력

10

출력

12

입력값 10에 대해 예상했던 것처럼 12가 출력되는 것을 확인할 수 있습니다. 이 알고리즘은 각 숫자를 한 번씩만 처리하므로 시간 복잡도는 O(N), 공간 복잡도 역시 O(N)입니다.