[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;
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}
}