자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(two pointers_연속된 자연수의 합)

 

 

5. 연속된 자연수의 합

 

예시 입력 1 

15

예시 출력 1

3

 

 

내가 푼 풀이(Time: 156ms Memory: 27MB)

강의 풀이에선 배열을 만들어서 자연수들을 담았는데, 그게 더 속도가 조금 빠르다.

계속 정수를 찾는것보다 데이터를 배열로 담는게 찾기가 더 빨라서 그런걸까?

import java.util.Scanner;

public class Main {
    public int solution(int n) {
        int answer = 0, lt = 1, sum = lt;
        for (int rt = 2; rt < n; rt++) {
            sum += rt;
            if (sum == n) answer++;
            while (sum >= n) {
                sum -= lt;
                lt++;
                if (sum == n) answer++;
            }
        }

        return answer;
    }

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

 

 

강의 풀이(Time: 152ms Memory: 27MB)

import java.util.Scanner;

public class Answer {

    public int solution(int n) {
        int answer = 0, sum = 0, lt = 0;
        // 연속된 2개 이상의 자연수 합이면, n/2 +1
        // 연속된 자연수로 합을 만들어야 하므로 n이 15일 경우 9이상은 등장할 수는 없다.
        int m = n / 2 + 1;

        int[] arr = new int[m];
        for (int i = 0; i < m; i++) arr[i] = i + 1;
        // 배열을 탐색하면 되서 m전까지!
        for (int rt = 0; rt < m; rt++) {
            sum += arr[rt];
            if (sum == n) answer++;
            while(sum >= n) {
                sum -= arr[lt++];
                if (sum == n) answer++;
            }
        }

        return answer;
    }

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

 

내 풀이보다 강의 풀이가 4ms더 빠른 이유?

 

• 데이터 구조의 차이:
  첫 번째 코드에서는 lt와 rt를 활용하여 구간을 이동하고, 이 두 변수를 통해 합을 계산합니다.
  두 번째 코드에서는 배열 arr을 사용하여 구간 내의 수를 저장하고 합을 계산합니다.
• 
  반복 횟수:
  첫 번째 코드에서는 lt와 rt가 각각 1부터 n-1까지 반복하므로 루프의 반복 횟수가 n-1번입니다.
  두 번째 코드에서는 lt와 rt가 각각 0부터 m-1까지 반복하므로 루프의 반복 횟수가 m번입니다. (m = n / 2 + 1)
• 
  배열 사용:
  두 번째 코드에서는 배열 arr을 사용하여 수를 저장하고 이를 활용하여 합을 계산합니다.
  첫 번째 코드에서는 lt와 rt를 사용하여 수를 직접 계산하고 저장하지 않습니다.

두 번째 코드가 더 빠른 이유는 반복 횟수가 적기 때문입니다. 두 코드 모두 시간 복잡도는 O(n)이지만, 실제로 두 번째 코드에서는 수행되는 반복 횟수가 더 적어서 더 빠르게 실행됩니다. 배열을 사용하여 합을 계산하는 것이 수학적으로 더 효율적이며, 이로 인해 두 번째 코드가 더 빠르게 동작합니다.