java - 연속된 자연수의 합 (투포인터)

import java.util.Scanner;

public class ConsecutiveNaturalNumber {
    public static int solution(int n) {
        int cnt = 0, lt = 0, sum = 0;
        int[] nums = new int[n / 2 + 1];
        for (int i = 0; i < nums.length; i++) nums[i] = i + 1;

        for (int rt = 0; rt < nums.length; rt++) {
            sum += nums[rt];
            if(sum==n) cnt++;
            while (sum >= n) {
                sum -= nums[lt++];
                if (sum == n) cnt++;
            }
        }
        return cnt;
    }

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

 

문제해결

---

 

이문제는 O(n)제곱의 시간복잡도를 O(n) 시간복잡도로 바꾸기 위한 문제이다.

이문제도 마찬가지로 연속된 수의 합을 구하기 때문에 sliding window방식으로 접근해야한다.

 

연속된 수의 배열을 만들 것인데 연속된 수의 배열의 가장큰 값은 n 을 2로 나눈 값의 +1 된 값이다.

예를 들어보자 15 가 들어왔을때 15를 2로 나눈뒤 +1을 더한 값이 8 이다

7 + 8 은 15이고 8 + 9 는 15를 넘기때문에 가장큰 값은 8이다.

 

1 부터 8까지 들어있는 배열을 만든다 left point 와 right point 두개를 두고 배열을 탐색한다.

sum 이라는 변수에 연속된 수의 합을 누적하고 n 과 같은지 비교한다. 같다면 cnt를 1증가 시키고 sum 이 n 보다 크거나 같을때

왼쪽 포인터가 가르키는 배열의 값을 빼고 1증가 시킨다.

 

그리고 나서 꼭 n과 같은지 비교해야한다.