문제
https://school.programmers.co.kr/learn/courses/30/lessons/12912?language=python3
문제 설명
두 정수 a, b가 주어졌을 때 a와 b 사이에 속한 모든 정수의 합을 리턴하는 함수, solution을 완성하세요.
예를 들어 a = 3, b = 5인 경우, 3 + 4 + 5 = 12이므로 12를 리턴합니다.
제한 조건
a와 b가 같은 경우는 둘 중 아무 수나 리턴하세요.
a와 b는 -10,000,000 이상 10,000,000 이하인 정수입니다.
a와 b의 대소관계는 정해져있지 않습니다.
풀이
문제 자체는 너무 쉽다.
그런데 어떻게 보면 효율적인 알고리즘에 대해 고민해볼 지점이 존재하기 때문에 따로 글로 남겨둔다.
def solution(a, b):
return sum(range(min(a, b), max(a, b) + 1))이렇게 하면 간단하게 풀이가 나온다.
def solution(a, b):
return sum(range(min(a, b), max(a, b) + 1))혹은 이렇게 코드를 짜면 두 정수의 대소관계에 대한 예외처리를 하지 않아도 된다.
하지만 이 코드는 O(n)의 시간복잡도를 가진다. a부터 b까지 모든 수를 순회해야 한다는 의미이다.
알고리즘을 구현할 때 더욱 효율적인 방법을 생각해보자.
여기서는 등차수열의 합 공식
등차수열의 합 공식을 활용하여 코드를 작성할 수 있다.
여기서 S는 등차수열의 합, a는 첫번째 항, l은 마지막 항, n은 항의 개수를 의미한다. 이를 이용하여 a와 b 사이의 정수 합을 구하는 코드를 작성할 수 있다.
def solution(a, b):
n = abs(b - a) + 1 # 항의 개수 계산
return (a + b) * n // 2 # 등차수열의 합 공식 적용이 코드는 입력값의 절대값을 계산하여 항의 개수를 구하고, 등차수열의 합 공식을 적용하여 결과를 반환한다. 이를 통해 O(1)의 시간 복잡도로 문제를 해결할 수 있다.
