프로그래머스 연습문제 - 두 정수 사이의 합

문제

두 정수 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의 대소관계는 정해져있지 않습니다.

해설

1. 반복문으로 풀기

 

def solution(a, b):
    answer = 0
    if (a == b):
        return a
    
    n = b if a > b else a
    m = a if a > b else b
    
    for i in range(n - 1, m):
        answer += i + 1
    return answer

 

둘 중 작은 숫자부터 큰 숫자까지 반복문으로 +1씩 하면서 answer에 더해가면서 정답 도출

반복문으로 풀었을 때 시간

 

하지만 시간복잡도가 O(n)이기 때문에, 두 정수 사이의 차이가 크면 시간복잡도가 증가한다.

 

2. 등차수열로 풀기

def solution(a, b):
    answer = 0
    if (a == b):
        return a
    
    n = b if a > b else a
    m = a if a > b else b
    
    if (m - n % 2 == 1):
        answer = (n + m) * (m - n + 1) / 2
    else:
        answer = (n + m) * (m - n) / 2 + n + (m - n) / 2
    return answer

 

둘 중 작은 수부터 큰 수까지 1씩 더해가기 때문에 등차수열의 합으로 풀어보자. 두 숫자의 양끝을 더해서 중간까지 더하는 식을 사용하면 위와 같이 도출할 수 있다.

등차수열로 풀었을 때 시간

 

같은 결과를 도출하지만, 시간 복잡도가 O(1)이므로 시간복잡도가 빨라진 것을 확인할 수 있다.