[프로그래머스]두 정수 사이의 합(JAVA)

문제 설명

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

• 예시

풀이

class Solution {
    public long solution(int a, int b) {
        long answer = 0;
        
        answer = sum(Math.max(a,b), Math.min(a,b));
        
        return answer;
    }
    
    public long sum(int a, int b){
        
        long total = 0;        
        if(a==b){
            total = a;
        }else{
            for(int i=b; i<=a; i++){
                total += i;
            }
        }       
        return total;
    }
}

• 실행 결과

다른 사람의 풀이

class Solution {

    public long solution(int a, int b) {
        return sumAtoB(Math.min(a, b), Math.max(b, a));
    }

    private long sumAtoB(long a, long b) {
        return (b - a + 1) * (a + b) / 2;
    }
}

for문을 이용해서 풀면 시간 복잡도가 O(n)이 되지만,
등차수열의 합을 이용해서 풀면 시간복잡도가 O(1)로 나온다.

등차수열의 합

등차수열의 합은 연속하는 두 항의 차이가 모두 일정한 수열을 뜻한다라는 정의를 가지고 있다.
제 n 항까지를 기준으로 항의 숫자의 합이 같다면 그 합은 일정하다고 말할 수 있다.

등차수열 방법 :

1. n(a+l)/2 == (개수(첫 항+끝 항)/2)
2. n(2a+(n-1)d)/2 == (개수(첫 항+(n항)*공차)/2

지금은 a~b의 정수의 합을 구하는 것이기 때문에 각 항의 공차는 1이다.
(b - a + 1) * (a + b) / 2
(b-a+1)은 항의 개수가 되고, (a+b)는 첫 항과 끝 항의 합이 된다.