[백준] 쉽게푸는문제 - 1292번

느낀점

메모리 효율성:

• 수열을 미리 생성하지 않고 필요한 부분만 계산하는 방식은 메모리를 효율적으로 사용합니다. 이는 특히 메모리 제한이 있는 환경에서 유용할 수 있습니다.

코드 간결성:

• 수열 생성과 구간 합 계산을 동시에 수행하는 접근 방식은 코드가 더 간결하고 이해하기 쉬운 구조를 제공합니다.

시간 효율성:

• 수열을 미리 생성하는 방식은 특정 상황에서 더 빠르게 구간 합을 계산할 수 있지만, 수열 생성 자체에 많은 시간이 소요될 수 있습니다.
• 메모리를 덜 사용하는 방식은 시간 복잡도가 더 높을 수 있습니다. 특히 입력 크기 B가 클 경우 성능에 영향을 미칠 수 있습니다.

문제 요구 사항과 실제 성능:

• 두 방식 모두 문제의 요구 사항을 만족하며, 실제 실행 시간과 메모리 사용량도 문제의 제한 내에 있습니다. 그러나 메모리를 절약하고, 코드 구조가 더 간결하여 유지보수에 유리한 방식이 있습니다.

이번에 코드 리팩토링을 통해서 리팩토링 전과 이후 두 접근 방식 모두 각각의 장단점이 있으며, 상황에 맞게 적절히 선택하는 것이 중요하다는 걸 느꼇습니다..

쉽게 푸는 문제

2 초	128 MB	35629	19790	17076	56.695%

문제

동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다.

이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다.

하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자.

입력

첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다.

출력

첫 줄에 구간에 속하는 숫자의 합을 출력한다.

예제 입력 1

3 7

예제 출력 1

15

코드1

//     메모리: 17608
//     시간: 208
package 쉽게푸는문제;

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

/*
        [시간 복잡도] : O(N^2)
 */

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 구간의 시작과 끝을 입력받습니다.
        int A = scanner.nextInt();
        int B = scanner.nextInt();
        scanner.close();

        // 수열 생성
        ArrayList<Integer> sequence = generateSequence(1000);

        // 구간의 합 계산
        int result = sumOfSubsequence(sequence, A, B);

        // 결과 출력
        System.out.println(result);
    }

    // 주어진 limit까지 수열을 생성합니다.
    public static ArrayList<Integer> generateSequence(int limit) {
/*
        1. 이 메소드는 수열의 크기 limit까지 생성합니다.
        2. 내부 루프에서 num이 증가할 때마다 해당 숫자를 num번 추가합니다.
        3. 결과적으로 전체 수열의 크기가 N일 때, 1 + 2 + 3 + ... + k가 N과 대략 같아야 합니다. 이는 대략적으로 k^2이 N에 비례하는 것을 의미합니다.
        4. 따라서, 이 메소드의 시간 복잡도는 O(N^2)입니다.
*/
        ArrayList<Integer> sequence = new ArrayList<>();
        int num = 1;
        while (sequence.size() < limit) {
            for (int i = 0; i < num; i++) {
                sequence.add(num);
            }
            num++;
        }
        return sequence;
    }

    // 수열의 A번째부터 B번째까지의 합을 계산합니다.
    public static int sumOfSubsequence(ArrayList<Integer> sequence, int A, int B) {
/*
    1. 이 메소드는 주어진 구간 [A, B]의 합을 계산합니다.
    2. 이 경우 시간 복잡도는 O(B - A)로, 최악의 경우 O(N)입니다.

 */
        int sum = 0;
        for (int i = A - 1; i < B; i++) {
            sum += sequence.get(i);
        }
        return sum;
    }
}

코드2

// memmory: 17688
// time: 204
package 쉽게푸는문제;

import java.util.Scanner;

// 시간 복잡도 => O(N^2)
public class Main2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int A = scanner.nextInt();
        int B = scanner.nextInt();
        scanner.close();

        int result = sumOfSubsequence(A, B);
        System.out.println(result);

    }
    static int sumOfSubsequence(int A, int B) {
        int sum = 0;
        int count = 0; // count 변수는 수열의 인덱스를 나타내며, 각 숫자가 몇 번 반복되었는지 추적합니다.

        for (int i = 1; i <= B; i++) {// 외부 반복문에서는 B번째 숫자까지의 합을 구하기 위해 1부터 B까지 반복합니다.
            for (int j = 0; j <= i; j++) {// 내부 반복문에서는 현재 숫자를 그 숫자만큼 반복하여 수열을 만듭니다.
                count++;// 반복하면서 count 변수를 증가시키고

                //  count가 A와 B 사이에 있는 경우에만 해당 숫자를 합에 추가합니다.
                if(count >=A && count <=B) sum += i;

                // B번째 숫자를 계산하고 나면 더 이상 계산할 필요가 없으므로 내부 반복문을 종료합니다.
                if(count == B) break;
            }
        }
        return sum;
    }
}

알고리즘 풀이법 및 코드 차이점

코드 1

알고리즘 개요:

• 주어진 구간 [A, B]의 수열을 미리 생성한 후, 해당 구간의 합을 계산합니다.
• 수열 생성은 generateSequence 메소드를 통해 이루어지며, 이 과정에서 수열의 모든 요소가 ArrayList에 저장됩니다.
• 이후 sumOfSubsequence 메소드를 통해 [A, B] 구간의 합을 계산합니다.

시간 복잡도:

• 수열 생성: O(N^2) (각 숫자를 해당 숫자만큼 추가하므로)
• 구간 합 계산: O(B - A) (최악의 경우 O(N))
• 전체 시간 복잡도: O(N^2)

코드 2

알고리즘 개요:

• 수열을 미리 생성하지 않고, 필요한 숫자를 즉석에서 계산하여 합을 구합니다.
• 외부 루프와 내부 루프를 통해 각 숫자가 반복되는 수만큼 수열에 접근하고, 카운트 변수를 이용하여 해당 구간 [A, B]의 합을 계산합니다.

시간 복잡도:

• 수열 생성 및 구간 합 계산을 동시에 수행: O(B^2) (최악의 경우 각 숫자가 반복되는 수만큼 내부 루프를 돈다)
• 전체 시간 복잡도: O(B^2)

차이점 요약

1. 수열 생성 방식:

• 코드 1: 전체 수열을 미리 생성하여 저장 후 구간 합을 계산.
• 코드 2: 필요한 숫자만 즉석에서 계산하여 구간 합을 계산.

메모리 사용:

• 코드 1: ArrayList를 사용하여 수열을 저장하므로 더 많은 메모리를 사용.
• 코드 2: 수열을 미리 저장하지 않으므로 메모리 사용이 적음.

시간 복잡도:

• 코드 1: 수열 생성에 O(N^2)의 시간이 소요되며, 구간 합 계산은 O(N).
• 코드 2: 수열 생성과 구간 합 계산을 동시에 수행하여 O(B^2).

결론

• 두 코드 모두 문제를 해결하는 데 적합하지만, 메모리 효율성과 코드 간결성을 고려할 때 코드 2가 더 유리합니다. 시간 복잡도에서 다소 불리할 수 있지만, 문제의 제한 내에서는 충분히 효율적으로 동작합니다. 코드 1은 대규모 수열을 미리 생성하는 접근 방식을 사용하여 특정 상황에서 더 빠를 수 있지만, 메모리 사용이 비효율적일 수 있습니다. 두 코드 모두 각각의 장단점이 있으며, 상황에 맞게 적절히 선택하는 것이 중요합니다.