문제

• 1부터 n까지의 1씩 증가하는 값들의 합을 구하는 함수 sum을 작성하세요.
• 예제

System.out.println(sum(10));  // 55 = 1+2+3+...9+10

풀이

public class Sum {
    public static void main(String[] args) {
        // long n = 1000000000L; // 10억
        // long n = 5000000000L; // 50억 --> sum1정상, sum2 overflow 발생
        long n = 10L;
        // long n = 10L;
        // long n = 9L;
        // long n = -1L;
        
        long startTime = System.currentTimeMillis();
        System.out.println("\nn:" + n + ", sum=" + sum1(n));
        System.out.println("estimated  time:" + (System.currentTimeMillis() - startTime));

        startTime = System.currentTimeMillis();
        System.out.println("\nn:" + n + ", sum=" + sum2(n));
        System.out.println("estimated  time:" + (System.currentTimeMillis() - startTime));
    }

    //  입력값, 출력값은 요구사항 정의 후 long으로 진행
    private static long sum1(long n) {
        // 입력값 검증을 수행하는지?
        if (n < 1) {
            // feature 도출시 n<1 일때 0 리턴 또는 runtimeException 이라고 정의하는지 면접자 확인
            System.out.println("오류 : 1이 1보다 작습니다. 0으로 응답합니다.");
            return 0L;
        }

        return (1+n)*n/2;
    }


    //  입력값, 출력값은 요구사항 정의 후 long으로 진행
    private static long sum2(long n) {
        // 입력값 검증을 수행하는지?
        if (n < 1) {
            // feature 도출시 n<1 일때 0 리턴 또는 runtimeException 이라고 정의하는지 면접자 확인
            System.out.println("오류 : 1이 1보다 작습니다. 0으로 응답합니다.");
            return 0L;
        }

        long sum = 0L;
        for (int i = 1; i <= n; i++) {
            // sum+=i; // 이렇게 코딩하면 overflow일때 음수가 출력됨. overflow에 대한 대책과 자료형에 대한 이해도 검증
            sum = Math.addExact(sum, i); // Exception in thread "main" javal.lang.ArithmeticException: long overflow
        }

        return sum;
    }
}

체크포인트

• n이 얼마나 큰 값인지, 정수인지 등에 대해 물어보는가? 또는 n의 범위를 한정하는가?
• 적당한 자료형을 선택하는가?
• int : -2,147,483,648 ~ 2,147,483,647 // 4바이트 –> 32비트 –> -2^31 ~ +2^31
• long : -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 // 8바이트 –> 64비트 –> -2^63 ~ +2^63
• n이 1보다 작을 경우 처리를 어떻게 할것인지에 대한 feature 정리하는지 확인
• 복잡도를 설명할 수 있는가?
• 구현 전/후 알고리즘을 제대로 설명하는가?
• 예외처리를 잘하는가?

풀이1 (sum1)

• 복잡도 O(1)
• 등차수열의 합 공식 (초등학생 가우스 풀이방식)
• 수학적 접근을 시도하는지 여부 검토

s  = 1     + 2     + ... + (n-1) + n
s  = n     + (n-1) + ... + 2     + 1
2s = (1+n) + (1+n) + ... + (1+n) + (1+n)
2s = (1+n)*n
s  = (1+n)*n/2

풀이2 (sum2)

• 복잡도 O(n)
• loop 수행하면서 sum
• 예외처리를 잘 하는지 검증