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

https://school.programmers.co.kr/learn/courses/30/lessons/12912#

프로그래머스

 

 

처음에는 작은 값부터 큰 값까지 for loop으로 더하려고 했습니다.

그런데 작은 값이 0보다 작은 경우, +- 합에 의해 사라지므로 0보다 작은 값을 더할 필요가 없다는 생각이 들었습니다. 그래서 작은 값과 큰 값의 부호에 따른 분기를 나눴습니다.

-100, -10 -> bigNum < 0
-100, 10 -> bigNum > 0, abs(smallNum) > abs(bigNum)
-100, 1000 -> bigNum > 0, abs(smallNum) <= abs(bigNum) 
10, 100 -> smallNum > 0

 

1 ~ n 까지의 합 공식인 n(n+1)/2가 떠올라서 (절댓값이 큰 값까지의 합 - 절댓값이 작은 값까지의 합)을 결과로 출력하기로 생각했습니다.

 

이 과정에서 edge 케이스와 분기 처리를 제대로 하지 않아 2시간 동안 원인을 찾지 못했습니다.

import kotlin.math.abs

class Solution {
    fun solution(a: Int, b: Int): Long {
        if (a == b) {
            return a.toLong()
        } else if (a == -b) {
            return 0
        }

        var smallNum = b
        var bigNum = a
        if (a < b) {
            smallNum = a
            bigNum = b
        }
        var mark = 1L

        if (bigNum > 0 && smallNum < 0) {
            if (abs(smallNum) > abs(bigNum)) {
                mark = -1
                val temp = bigNum
                bigNum = smallNum * -1
                smallNum = temp
            } else if (abs(smallNum) < abs(bigNum)) {
                smallNum *= -1
            } else {
                return 0
            }
        } else if (bigNum < 0) {
            mark = -1
            bigNum *= -1
            smallNum *= -1
        } else {
            smallNum -= 1
        }

        val bigRes = bigNum  * (bigNum + 1) / 2L
        val smallRes = smallNum * (smallNum+1) / 2L
//        println("$bigNum $bigRes and $smallNum $smallRes")
        return mark * (bigRes - smallRes)
    }
}

 

위 코드에서 뭐가 문제일까요?

1. smallNum과 bigNum은 a와 b를 그대로 대입받아 Int 타입입니다. a와 b의 값이 매우 클 경우 합 공식을 적용할 때 overflow가 발생하여 정확하지 않은 값이 나옵니다.
   ex) -1, 10000000
2. smallNum과 bigNum 모두 0보다 작은 경우(  bigNum < 0 block )
   smallNum의 절댓값이 bigNum의 절댓값보다 큼에도, 두 숫자를 바꾸지 않아 결괏값이 음수가 아닌 양수가 되었습니다.
   또한 절댓값이 작은 값의 음수를 포함하기 위해 1을 빼주지 않았습니다.

이 2가지 문제를 해결하면 아래와 같이 됩니다.

import kotlin.math.abs

class Solution {
    fun solution(a: Int, b: Int): Long {
        if (a == b) {
            return a.toLong()
        } else if (a == -b) {
            return 0
        }

        var smallNum = b.toLong()
        var bigNum = a.toLong()
        if (a < b) {
            smallNum = a.toLong()
            bigNum = b.toLong()
        }
        var mark = 1L // 두 숫자를 모두 절댓값으로 만든 다음, 결괏값에 부호를 결정하기 위한 변수

        if (bigNum > 0 && smallNum < 0) {
            if (abs(smallNum) > abs(bigNum)) { // -100, 10
                mark = -1L
                val temp = bigNum
                bigNum = abs(smallNum)
                smallNum = temp
            } else if (abs(smallNum) < abs(bigNum)) { // -100, 1000
                smallNum *= -1
            } else {
                return 0
            }
        } else if (bigNum < 0) { // -100, -10
            mark = -1L
            val temp = abs(bigNum)
            bigNum = abs(smallNum)
            smallNum = temp - 1  // 절댓값이 더 작은 숫자도 포함하기 위해 1을 뺌
        } else {
            smallNum -= 1 // smallNum도 포함하기 위해 1 뺌
        }

        // 1 ~ n 합 공식 적용 : n(n+1)/2
        val bigRes = bigNum * (bigNum + 1) / 2L
        val smallRes = smallNum * (smallNum + 1) / 2L
        return mark * (bigRes - smallRes)
    }
}

 

다른 분들의 코드를 보고 제 코드가 비효율적임을 알았고, 이것은 등차수열의 합 공식의 원리를 이해하지 못해서 발생했습니다.

등차수열의 합 공식은 아래와 같습니다.

여기서 n은 항의 갯수, a는 첫 항, l은 마지막 항입니다.

따라서 이전 코드와 같이 1부터 n까지의 합을 계산하는 것이 아니라, 작은 값부터 큰 값까지의 합을 바로 계산할 수 있습니다.

class Solution {
    fun solution(a: Int, b: Int): Long {
        if (a == b) {
            return a.toLong()
        } else if (a == -b) {
            return 0
        }

        var smallNum = b.toLong()
        var bigNum = a.toLong()
        if (a < b) {
            smallNum = a.toLong()
            bigNum = b.toLong()
        }

        return (bigNum - smallNum + 1) * (bigNum + smallNum) / 2
    }
}