#001 기본 수열 구하기

문제) 1 부터 100까지의 수를 구하여라

package dataStructure.prediction;

public class SequenceSum {

    public static void main(String[] args) {

        // TODO Auto-generated method stub

       int sum = 0;

       for(int i=1; i<=100;i++) {

            sum += i;

       

       }

       System.out.println("sum = "+sum);

    }

}

물론 위와같이 짜도 된다. timeComplex는 O(n)임.

하지만 기술면접에서 저렇게 쓰면 합격은 기대하지 말자

이를 개선하기 위해 천재적인 수학자 가우스의 등차수열 이론을 활용하자

이 이론은 1 ~ 100까지 더하는 것은 결국

(100 + 1) + (99 + 2) + (98 + 3) …. (3 +98) + (2 + 99) + (1 + 100)의 합과 동일하다.

두 합을 더한 결과인 101을 50번 곱하는 결과와 1~100을 모두 더한 결과는 같다

수식으로 하면 아래와 같다

int max = 100;

(max + 1) * (max/2) = 1…max의 더한값

package dataStructure.prediction;

public class SequenceSum {

    public static void main(String[] args) {

        // TODO Auto-generated method stub

       int sum = 0;

       int maxSize = 100;

       for(int i=1; i<=maxSize;i++) {

            sum += i;

       

       }

       System.out.println("sum = "+sum);

       int gauseSum = (maxSize+1) * (maxSize/2);

       System.out.println("gauseSum = "+gauseSum);

      

    }

}

활용 문제) 10억까지 정렬되지 않은 임의의 수를 저장한 배열이 있다.

10억 중에 임의의 수 하나가 빠졌는데 이를 구하시오.

이문제 역시 가우스 이론을 이용하면 되는데

10억까지의 합을 구한 후 배열의 순차탐색(O(n))하여 숫자를 빼나간다.

마지막 남은 수가 빠진 수.

      

long bigDataMaxSize = 1000000000L;

long bigSum = (bigDataMaxSize+1) * (bigDataMaxSize/2);

System.out.println(bigSum);

이 공식을 구현할때 최대 수를 표현할 수 있는 long을 사용한다.

단 이러한 방식으로 구할 수 있는 최대 수는 10억이다. (sum값을 구할때 곱하기 때문에 long의 최대 범위를 벗어남)

따라서, 10억이상의 수를 구할 수 있는 방법은 패턴을 뽑아내는 것이다.

100까지의 합은 5050 (101 * 50).

1000까지의 합은 500500 (1001 * 500)

10000까지의 합은 50005000 (10001 * 5000)

패턴이 보이지 않는가?

1 * (maxSize/2) = 구한 결과를 문자열로 변환 후

앞 머리에 똑같이 붙임.

이를 Long.valueOf로 변환.

이렇게 하면 100억이상은 물론, 조, 경단위까지 계산 가능함.

*물론, maxSize가 다른 값이면 패턴이 달라진다는건 함정.ㅎㅎㅎ