프로그래머스 - 두 정수 사이의 합

비도 추적추적 오고 발목도 다쳐 운동도 못하게 되며 심심한데 프로그래머스를 처음부터 풀어보자!

라는 생각으로 문제를 풀게 되었습니다.

 

주어진 두 수(a, b)가 존재할 때, a부터 b까지의 합을 도출해 내야 하는 문제였습니다.

이전에는 브루트 포스로 접근하여 해결했지만, 테스트 케이스가 추가되며 해결 방식이 달라졌는데요.

 

문제의 제한조건이 -10,000,000 ~ 10,000,000이었기 때문에

반복문이나 재귀함수를 통한 접근은 성능 문제가 발생할 것으로 예상했습니다.

예상대로 while문을 사용한 반복문으로는 테스트 케이스에서 실패가 발생했고 다른 방식으로

문제 해결에 접근이 필요했어요.

 

개쩌는 공식 발견인 줄 알았는데 알고 보니 고등학교 때 배운 등차수열이었고ㅋㅋㅋ

사실, 결론부터 말하자면 고등학교 때 배웠던 등차수열로 해결 가능했습니다.

완전히 잊고 살았던 개념이었는데, 수학을 왜 다시 배워야 하는지에 대해 깨닫게 되었어요..!

 

2, 3, 4, 5, 6, 7이라는 수열이 존재한다고 가정해 보겠습니다.

첫 항인 2와 마지막 항인 7을 더하면 9. 다음 순서로 3과 6을 더하면 9.

그다음으로 4와 5를 더하면 9.. 일련의 규칙이 존재했습니다.

9가 3번 나타나고, 모두 더하면 27이라는 수가 도출됩니다.

 

그런데 위에서 주어진 두 수 사이의 나머지 항도 고려해야 했는데요.

잠깐.. 항의 개수 * (첫항 + 마지막 항)을 통해 동일하게 정답인 27의 2배인 54라는 수가 도출됩니다.

위의 수열에서 항의 개수는 어떻게 파악할까를 고민했을 때, 첫 항과 마지막 항을 빼고

1을 더해주니 항의 개수와 동일했습니다.

(7-2)+1 = 6

 

항의 개수는 구했으니 계산을 해보자면 6 * (2+7) = 54라는 값을 얻을 수 있는데요.

27이라는 수를 구해야 하는데 54라는 수를 구했습니다.

그런데 54.. 에서 2를 나누게 되면 27이 되더라고요.

하나의 케이스에서만 적용되는 것인지 검증이 필요해 다른 수열을 예시로 테스트해 봤습니다.

 

다른 예시로 검증해 보자

첫 항이 11, 마지막 항이 19라고 예시를 들어보겠습니다.

11, 12, 13, 14, 15, 16, 17, 18, 19로 9개의 항이 존재하고 (19-11)+1을 통해 항의 개수를 9개로

동일하게 얻을 수 있었습니다.

 

수열의 총합은 135, (9 * (11+19)) / 2 = 135로 수열의 합에 대한 값을 동일하게 얻을 수 있습니다.

개쩌는 규칙을 발견한 줄 알았지만 알고 보니 고등학교 때 배웠던 등차수열이었네요,,

문제를 해결하고 타 블로그를 보며 등차수열에 대한 개념을 오랜만에 체크했고

제가 접근한 방식이 가우스의 덧셈 공식이라고 불리는 개념이라는 것도 알게 되었습니다.

참 똑똑한 사람들 많습니다 정말..

 

제출 코드

function solution(a, b) {
    if(a === b) return a;
    
    const min = Math.min(a,b);
    const max = Math.max(a,b);
    const length = (max-min)+1;
    
    return (length*(min+max)) / 2;
}

 

 

요약

등차수열의 합을 구하는 본질은 평균값 X 항의 개수이다.

항의 개수 * (첫 항 + 마지막 항) / 2

 

Reference

코딩 관련 지식 - 등차수열이란