자바 알고리즘 문제 풀이 입문. 섹션3. Two Pointers, Sliding Window [효율성 : O(n^2) --> O(n)] : 연속된 자연수의 합

 

https://hyejin.tistory.com/1223

-> 이전 문제 풀이 

 

 

5. 연속된 자연수의 합 

설명

N입력으로 양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수를 출력하는 프로그램을 작성하세요.

만약 N=15이면

7+8=15

4+5+6=15

1+2+3+4+5=15

와 같이 총 3가지의 경우가 존재한다.

 

입력

첫 번째 줄에 양의 정수 N(7<=N<1000)이 주어집니다.

 

출력

첫 줄에 총 경우수를 출력합니다.

 

예시 입력 1 

15

 

예시 출력 1

3

 

 

문제 풀이 1

public int solution(int n) {
    int answer = 0, sum;
    for (int i = 1; i <= n; i++) {
        sum = i;
        for (int j = i + 1; j <= n - i; j++) {
            sum += j;
            if (sum == n) {
                answer++;
                break;
            } else if (sum > n) {
                break;
            }
        }
    }
    return answer;
}

👩🏻‍💻 : 나는 우선 저번 문제 풀이와 동일하게 풀었다. 이중 for 문을 이용해서 첫번째 for문에서는 더할 첫번째 수를 구하고, 두번째 for문에서는 그 첫번째수 다음부터 값을 더하는데 이때 sum이 n과 값이 같다면 answer 에 +1 해주고 break 하고 다음 첫번째 수로 넘어가고,,, 

sum이 n보다 크면 바로 break문으로 나오도록 했다. 

 

 

 

문제 풀이 2

public int solution2(int n) {
    int answer = 0, sum =0;
    int lt = 0;
    int m = n / 2 + 1;
    int[] arr = new int[m];
    for (int i = 0; i < m; i++) {
        arr[i] = i + 1;
    }

    for (int rt = 0; rt < m; rt++) {
        sum += arr[rt];
        if (sum == n) {
            answer++;
        }

        while (sum >= n) {
            sum -= arr[lt++];

            if (sum == n) {
                answer++;
            }
        }
    }


    return answer;
}

👾 : 강사님은 우선 배열을 새로 하나 만들었는데 이때 배열의 크기는 n / 2 + 1 로 설정했다. 그 이유는 어차피 n / 2 + 1 뒤에 연속된 값들을 더해봤자 n 값을 넘어가기 때문에 구할 필요가 없기 때문이다. 그 다음 반복문을 통해 1 ~ n 값을 배열에 담아준다. 

 

그 다음은 이전 문제 풀이와 동일하게 진행하는데 먼저 sum 에 arr[rt] 값을 더한다음, sum과 n 값을 비교하고, 같으면 answer +1 n보다 크면 while문을 돌면서 sum에서 arr[lt] 값을 빼준 다음 lt + 1 해준다. 그 다음 이 sum 을 다시 n과 비교하고... 이렇게 반복하다보면 sum 이 n인 연속된 숫자의 합은 몇개인지를 알 수 있다.