[프로그래머스] Lv0. 연속된 수의 합

문제

 

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/120923

---

원리

* total이 양의 정수일 때도 있지만, 음의 정수일 때도 있다는 점

* total = 양의정수 + 음의정수 로 구성될 수도 있다는 점

---

풀이방법

/**
 *
 * 1. 1부터 n까지의 합 = n*(n+1) / 2
 * 2. 등차수열의 합 = n ( 2a + (n-1)d )   : 여기서 a는 시작 수, d는 공차
 * 3. 실제 시작점. 음수일 경우를 포함한 등차수열의 합은 num개의 합산만큼 뺀 수에서 구함 (여기가 키포인트)
 */

---

나의 코드

1. 브루트포스 [ 실패 ]

: 위의 주의사항을 생각 못하고 작성했던 코드

public static int[] solution(int num, int total) {
        int[] answer = new int[num];
        int ready = total;
        int sum = 0;
        while (sum != total) {
            sum = 0;
            int now = ready;
            answer = new int[num];
            for (int i = num - 1; i >= 0; i--) {
                sum += now;
                answer[i] = now;
                now--;
//                if(sum>total) break;  // 만약 이 코드 실행 시, -1를 포함하여 합산이 가능한 경우가 포함되지 않는다.
            }
            ready--;
        }

        return answer;
    }

 

2. 중앙값을 통한 비교 방식 [ 실패 ]

public static int[] solution(int num, int total) {
    /**
     * 1. num이 홀수일때는 중앙값, 짝수일땐 num/2의 값
     * 2. total/num의 내림이 중앙값
     * 3. 만약 total/num이 0이면, total%num이 처음값
     */
    int[] answer = new int[num];

    if(total/num==0) {
        int start = total%num;
        for(int i=0; i<answer.length; i++) {
            answer[i] = start;
            start++;
        }
    }
    else{
        if(num%2!=0) {
            int center = (int) Math.floor(total/num);
            int minus = (int) Math.floor(num/2);
            int start = center - minus;
            for(int i=0;i<answer.length;i++) {
                answer[i] = start;
                start++;
            }
        } else {
            if(total>=0) {
                int center = Math.abs(total / num);
                int minus = (int) Math.floor(num / 2) - 1;
                int start = center - minus;
                for (int i = 0; i < answer.length; i++) {
                    answer[i] = start;
                    start++;
                }
            } else {
                int center = Math.abs(total / num);
                int start = center;
                for (int i = answer.length-1; i >= 0 ; i--) {
                    answer[i] = start;
                    start--;
                }
            }
        }
    }
    System.out.println(answer);
    return answer;
}

 

3. 등차수열의 합 1차 [ 실패 ]

: 접근은 맞으나, total이 음수일 경우를 미포함

public static int[] solution(int num, int total) {
    /**
     *
     * 1. 1부터 n까지의 합 = n*(n+1) / 2
     * 2. 등차수열의 합 = a * d * (0부터 n-1까지의 합)   : 여기서 a는 시작 수, d는 공차
     * 3. 등차수열의 합 = a + (a * d * ( (n-1) * n / 2 ))
     * 4. 따라서, total = a + (a * 1 * ( (num-1) * num /2 )) = a(1 + ((num-1) * num /2 ))
     * 5. 이때, a = total / (1 + ((num-1) * num /2 ))
     */
    int[] answer = new int[num];
    int startA = total / (1 + ((num-1) * num /2 ));
    for(int i = 0 ; i < num ; i++) {
        answer[i] = startA;
        startA++;
    }

    return answer;
}

 

4. 등차수열의 합 + 음수일 경우 [ 성공 ] 

public static int[] solution(int num, int total) {
    int[] answer = new int[num];

    int sum = num * (1 + num) / 2; // num개의 수를 공차 1로 합산한 수
    int start = (total - sum) / num;  // 실제 시작점. 음수일 경우를 포함한 등차수열의 합은 num개의 합산만큼 뺀 수에서 구
    for(int i=0; i<num; i++){ answer[i] = i + 1 + start; }

    return answer;
}

---

레퍼런스 코드

참고 링크 : https://velog.io/@kim11401/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%97%B0%EC%86%8D%EB%90%9C-%EC%88%98%EC%9D%98-%ED%95%A9-Java