[Java] 연속된 자연수의 합

문제

 

우선 연속된 원소와 관련된 문제라서 투포인터와 슬라이딩을 문제임을 알 수 있다. 더하는 자연수의 갯수가 변할 수 있으므로 투포인터 알고리즘을 이용해서 푸는 문제이다.

주의할점

다른 문제와 다르게 배열이 주어지지 않았다. 따라서 배열을 선언해야되는데 길이를 정해야 한다. 예를들어 N=15라 가정한다. 그럼 첫 원소값이 7이면 7+8로 가능한 경우가 있지만 8이 되면 가능한 경우가 사라지게 된다. 따라서 배열의 길이는 N/2+1로 설정해야한다.

 

그리고 투포인터 알고리즘은 구조적으로 패턴이 정해져 있다. 따라서 패턴을 기억하도록 하자.

 

코드

package 인프런.투포인터와슬라이딩윈도우.연속된자연수합.방법2;

import java.util.Scanner;

/*
* 연속 --> 투포인터 or 슬라이딩 --> 배열 길이 변화 --> 투포인터 알고리즘 사용
* 입력 최대가 999이고 2개 이상 연속된 자연수의 합이므로 1부터 500을 갖는 배열 선언
* for문의 경우 시간복잡도가 성능이 안좋으므로 투포인터 알고리즘 사용
*
* */
public class Main {
    public int solution(int n) {
        int answer=0;
        int sum=0;
        int start = 0;
        int m=n/2+1;
        int[] arr = new int[m];

        for (int i=0; i<m; i++)
            arr[i] = i+1;

        for (int end=0; end < m ; end++) {
            sum+=arr[end];
            if (sum ==n)
                answer++;
            while (sum>=n) {
                sum -= arr[start++];
                if (sum == n)
                    answer++;
            }
        }
        return answer;
    }

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

 

느낀점

전형적인 투포인터 문제다. 구조를 이해하는게 중요하다.