[알고리즘] 프로그래머스 : 두 정수 사이의 합

알고리즘 문제 출처 : 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/12912

프로그래머스

 

내가 작성한 코드

반복문을 돌릴까 생각도 했지만 수의 범위가 -10,000,000 이상 10,000,000 이하인 정수이고 넓은 범위가 걸리면 시간 복잡도가 높아질 것 같아서 반복문을 피하고자 했다.

따라서 가우스의 덧셈에 의해 1~n까지의 합을 n(n+1)/2 로 구할 수 있는 것에서부터 출발했다. a~b까지의 합은 1~b까지의 합에서 1~a까지의 합을 빼주고 더해주면 된다. 하지만 이건 갖가지 경우마다 다르게 계산해줘야 해서 1) 두 수가 같은 경우 2) 두 수가 모두 양수인 경우 3) 두 수가 모두 음수인 경우 4) 하나는 음수, 하나는 양수인 경우 5) 하나는 0이고 하나는 0이 아닌 경우로 나누었고 케이스를 더 세분화하여 코드를 짰다.

class Solution {
    public long solution(int a, int b) {
        long answer = 0;
        long absA = Math.abs(a);
        long absB = Math.abs(b);
        long sumA = absA * (absA + 1) / 2;
        long sumB = absB * (absB + 1) / 2;
        if(a == b) answer = a; 
        else if(a > 0 && b > 0){ 
        	answer = Math.abs(sumA-sumB) + Math.min(a, b);
        }
        else if(a < 0 && b < 0){ 
        	answer = -Math.abs(sumA-sumB) + Math.max(a, b);
        }
        else if(a < 0 && b > 0){
        	answer = sumB - sumA;
        }
        else if(a > 0 && b < 0) {
        	answer = sumA - sumB;
        }
        else if(a == 0 && b != 0) {
        	if(b > 0) answer = sumB;
        	if(b < 0) answer = -sumB;
        }
        else if(b == 0 && a != 0) {
        	if(a > 0) answer = sumA;
        	if(a < 0) answer = -sumA;        	
        }
        return answer;
    }
}

 

이렇게 풀고 나서 다른 사람들은 어떻게 풀었을지 궁금해서 찾아봤는데 등차수열의 합으로 간단하게 문제를 푼 걸 봤고 신기했다. 이렇게 간단하게 코드를 짤 수 있다니. 프로그래밍도 프로그래밍이지만 수학이 이렇게 유용하게 쓰일 수 있다는 걸 다시 깨닫게 됐다.

그래도 제대로 된 알고리즘은 처음 풀어본 거니까 앞으로 계속 발전할 나를 기대해본다. 문제 유형을 많이 접하다 보면 사고도 확장되고 다양한 프로그래밍을 구현해낼 수 있으리라 믿는다.