[알고리즘] Two pointers, Sliding window(5) : 연속된 자연수의 합(JAVA)

👔 문제

🩳 풀이

2중 for문으로 풀지 말자! 시간 복잡도가 커진다.

🔑 풀이1 Two pointer 방법

위에서 했던 방법과 일치한다.

배열의 크기는 입력값 N의 N/2 + 1 만큼 해준다.
배열

arr[0] = 1, arr[1] = 2, arr[2] = 3, arr[3] = 4 ,...

배열의 값은 위와 같은 식으로 넣어 준다.

public int solution(int n){
        int answer= 0, sum =0, 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++;
            }
        }     

• 배열 m의 크기는 입력값 n/2+1 의 크기 만큼 만들어 준다.
• arr[0]=1, arr[1]=2; arr[2]=3, ....을 for문을 이용해서 저장해준다.
• rt의 값을 ++해가면서 sum에 저장한다.
• 만약 sum == n 이면 answer++
• sum >= n 이면 현재 lt의 값을 빼고 lt++을 해준다.
• lt를 뺀 sum의 값이 n과 같다면 answer++;

🔑 풀이2 수학적 방법

생각 순서

• 연속해서 2개의 합이 15가 되는지 확인 하기 위해서 각 자리는 1의 차이를 갖는 다는 것을 알 수 있다.
• 2개 연속일때 2칸을 만들어 놓고 각각 숫자 1과 2를 넣어준다.
• 15-(1+2) = 12 이고 이는 각각의 칸에 6씩 나누어 가질 수 있다.
• 1+6 , 2+6 즉, 7,8 연속된 두 개의 숫자의 합으로 15를 표현할 수 있다.

• 연속해서 3개의 합이 15가 되는지 확인 하기 위해서는 각자리는 1의 차이를 갖는 다는 것을 알 수 있다.
• 3개 연속일때, 3칸을 만들어 놓고 각각 숫자 1,2,3을 넣어준다.
• 15-(1+2+3) = 9 이고, 이는 각각의 칸에 3씩 나누어 가질 수 있다.
• 3+1, 3+2, 3+3 즉, 4,5,6의 합은 15이므로 연속된 세 개의 숫자의 합으로 15를 만들 수 있다 .

위와 같은 수학적인 방법으로 문제를 풀 수 있다.

public int solution(int n){
	int answer = 0, cnt = 1;
    n--;
    while(n>0){
    	cnt++;
        n = n -cnt;
        if(n%cnt ==0) answer++;
    }
    return answer;
}

🧦 소스코드

👢twopointer 방법

package algolecture;

import java.util.Scanner;

public class Main29 {

    public int solution(int n){
        int answer= 0, sum =0, 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;
    }

    public static void main(String[] args) {
        Main29 T = new Main29();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        System.out.print(T.solution(n));
    }


}

🥾수학적 방법

package algolecture;
import java.util.Scanner;

public class Main29math {
    public int solution(int n){
        int answer = 0, cnt = 1;
        n--;
        while(n>0){
            cnt++;
            n= n-cnt;
            if(n%cnt==0) answer++;
        }
        return answer;
    }

    public static void main(String[] args) {
        Main29math T = new Main29math();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        System.out.print(T.solution(n));
    }
}