[JAVA] 수들의 합5

 

투포인터

https://www.youtube.com/watch?v=rI8NRQsAS_s 

투포인터,구간합 알고리즘 강의 나동빈

처음에는 투포인터 문제인지 모르고 풀었다.

그 풀이는 아래와 같다.

 

풀이 한 코드가 너무 아까워서 남겨둔 것이니, 투포인터 풀이를 보려면 더 아래로 내려가서 확인하면 된다.

import java.util.*;
import java.io.*;


public class Main {
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(br.readLine());

        //n(n+1)/2 = n
        int count = 1;//1가지는 무조건있음
        for (int i = 2; i < n; i++) {
            int div = n / i;

            if (find(i, div)) {
                count++;
            }
        }
        System.out.println(count);
    }

    public static boolean find(int plusMinus, int center) {

        //center 중심으로 +-
        if (plusMinus % 2 == 0) {//짝수인경우 플러스나 마이너스 한쪽 한개많음
            int range = (plusMinus) / 2;
            if ((center + range < n && center - (range - 1) > 0)
                    && getSum(center - (range - 1) , center + range) == n)
                return true;//오른쪽으로 두칸 왼쪽 한칸
            if (center - range > 0 && center + (range - 1) < n
                    && getSum(center - range, center + (range - 1)) == n) {//왼쪽 두칸 오른쪽 한칸
                return true;
            }
        } else {
            int range = (plusMinus - 1) / 2;
            if (center + range < n && center - range > 0
                    && getSum(center - range, center + range) == n) {
                return true;
            }
        }

        return false;
    }

    public static int getSum(int start, int end) {
        int sum = 0;
        for (int i = start; i <= end; i++) {
            sum += i;
        }
        return sum;
    }

}

 

투포인터 풀이

import java.io.*;


public class Main {
    static int n, count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        
        twoPointer();
        System.out.println(count);
    }

    public static void twoPointer() {
        int left = 0, right = 0, sum = 0;
        while (left <= n) {
            while (++right <= n) {
                sum += right;
                if (sum >= n) {
                    if (sum == n) count++;
                    break;
                }
            }
            while (++left <= n) {
                sum -= left;
                if (sum <= n) {
                    if (sum == n) count++;
                    break;
                }
            }
        }
    }
}