[ 파이썬(python) ] 백준 1009 - 분산처리

📍 백준 1009 - 분산처리

백준 1009 - 분산처리

---

⚡️ 나의 풀이

문제 자체는 어렵지 않았다. 단순하게 a ** b % 10을 구하면 되는 문제였는데, 2가지를 신경 쓰지 못했다.

 

1. 정수 b의 범위: 1 <= b < 1,000,000인데, 거듭제곱형태라서 나중에 값이 기하급수적으로 커지게 된다.
2. a ** b % 10: 만약, a ** b가 10이 나오면 0이 출력되기 때문에 따로 조건을 넣어줘야 한다.

 

1번은 ** 대신 pow 내장 함수를 이용했는데 결론적으로 x ** y의 시간 복잡도는 O(N)이고, pow(x, y)의 시간복잡도는 O(1)이다. 왜 그런지는 스택오버플로우 질문을 참고하자. 그리고 pow함수에서 세 번째인자까지 넘겨 줄 수 있는데 pow(base, -exp, mod) 세번째 인자는 mod연산을 할 수 있다.

 

2번은 x % 10를 할 때 10 % 10이면 0이 되므로 0일 때는 10을 더해주는 조건을 추가했다.

 

T = int(input())

for _ in range(T):
    a, b = map(int, input().split())
    result = pow(a, b, 10)
    if not result:
        print(result+10)
    else:
        print(result)

 

여담으로 x ** y, pow(x, y), math.pow(x, y) 함수 중 제일 빠른 함수는 math.pow(x, y)인데, 다음 코드를 한번 실행하면 곧장 알 수 있다.

 

import timeit

def show_timeit(command, setup):
    print(setup + '; ' + command + ':')
    print(timeit.timeit(command, setup))
    print()

# Comparing small integers
show_timeit('a ** b', 'a = 3; b = 4')
show_timeit('pow(a, b)', 'a = 3; b = 4')
show_timeit('math.pow(a, b)', 'import math; a = 3; b = 4')

# Compare large integers to demonstrate non-constant complexity
show_timeit('a ** b', 'a = 3; b = 400')
show_timeit('pow(a, b)', 'a = 3; b = 400')
show_timeit('math.pow(a, b)', 'import math; a = 3; b = 400')

# Compare floating point to demonstrate O(1) throughout
show_timeit('a ** b', 'a = 3.; b = 400.')
show_timeit('pow(a, b)', 'a = 3.; b = 400.')
show_timeit('math.pow(a, b)', 'import math; a = 3.; b = 400.')