[알고리즘] 3-5 연속된 자연수의 합 - two pointers 알고리즘(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 간략한 문제 설명, 예습 풀이 코드, 강의에서 설명하는 풀이 코드를 정리하고 있습니다.

• 문제 링크 : https://cote.inflearn.com/contest/10/problem/03-05
• 문제 설명 : n입력으로 양의 정수 n이 입력되면 2개 이상의 연속된 자연수의 합으로 정수n을 표현하는 방법의 가짓수를 출력하는 문제

예습 풀이

• two pointers 알고리즘 사용
• 반복문의 종료 조건 : 2개의 수가 연속될 때 합이 n보다 큰 경우

package inflearn.tow_pointers_sliding_window;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//연속된 자연수의 합
public class Main3_5 {

    public static int solution(int n) {
        int left = 1, sum = 1, answer = 0;

        for (int right = 2; right < n; right++) {
            sum += right;

            if (sum == n) {
                answer++;
            }

            //종료 조건 
            if ((right-left) == 1 && sum >= n) {
                break;
            }

            while (sum > n) {
                sum -= (left++);
                if (sum == n) {
                    answer ++;
                }
            }
        }

        return answer;
    }

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

        System.out.println(solution2(n));
    }
}

강의 복습 풀이

• 마찬가지로 two pointers 알고리즘 사용
• 반복문의 종료 조건 : right가 n을 2로 나눈 몫에 +1한 값이 될때까지만 반복
• 배열 사용

public static int solution2(int n) {
    int left = 0, sum = 0, answer = 0;
    int m = n/2 + 1; //n을 2로나눈 몫에 + 1한 값 까지만 연속된 자연수가 있으면된다.
    int[] arr = new int[m];

    //배열 초기화
    for (int i = 0; i < m; i++) {
        arr[i] = i + 1;
    }

    for (int right = 0; right < m; right++) {
        sum += arr[right];

        if (sum == n) {
            answer++;
        }

        while (sum > n) {
            sum -= arr[left++];

            if (sum == n) {
                answer++;
            }
        }
    }

    return answer;
}