[LeetCode] - 2894. Divisible and Non-Divisible Sums Difference

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Divisible and Non-Divisible Sums Difference" 문제입니다.

-->  https://leetcode.com/problems/divisible-and-non-divisible-sums-difference/description/

 

문제 : 

You are given positive integers n and m.

Define two integers, num1 and num2, as follows: num1 : The sum of all integers in the range [1, n] that are not divisible by m.

num2 : The sum of all integers in the range [1, n] that are divisible by m.

Return the integer num1 - num2.

---

Example 1 :

Input : n = 10, m = 3

Output :19

Explanation : In the given example:

- Integers in the range [1, 10] that are not divisible by 3 are [1,2,4,5,7,8,10], num1 is the sum of those integers = 37.

- Integers in the range [1, 10] that are divisible by 3 are [3,6,9], num2 is the sum of those integers = 18. We return 37 - 18 = 19 as the answer.

 

Example 2 :

Input : n = 5, m = 6

Output : 15

Explanation: In the given example:

- Integers in the range [1, 5] that are not divisible by 6 are [1,2,3,4,5], num1 is the sum of those integers = 15.

- Integers in the range [1, 5] that are divisible by 6 are [], num2 is the sum of those integers = 0.

We return 15 - 0 = 15 as the answer.

 

Example 3 :

Input : n = 5, m = 1

Output : -15

Explanation : In the given example:

- Integers in the range [1, 5] that are not divisible by 1 are [], num1 is the sum of those integers = 0.

- Integers in the range [1, 5] that are divisible by 1 are [1,2,3,4,5], num2 is the sum of those integers = 15.

We return 0 - 15 = -15 as the answer.

 

Constraints : 1 <= n, m <= 1000

---

이 문제를 요약하자면 :

 

주어진 양의 정수 n과 m에 대해 다음 두 가지 정수를 정의합니다 :

• num1: [1, n] 범위에서 m으로 나누어지지 않는 모든 정수의 합
• num2: [1, n] 범위에서 m으로 나누어지는 모든 정수의 합

최종적으로 num1 - num2를 반환합니다.

class Solution {
    public int differenceOfSums(int n, int m) {
        List<Integer> num1s = new ArrayList<>();
        List<Integer> num2s = new ArrayList<>();

        int num1 = 0;
        int num2 = 0;

        for (int i = 1; i <= n; i++) {
            if (i % m == 0) {
                num2s.add(i);
            } else {
                num1s.add(i);
            }
        }

        for (int i : num1s) {
            num1 += i;
        }

        for (int j : num2s) {
            num2 += j;
        }

        return num1 - num2;
    }
}

 

제 코드는 되게 심플하게 작동합니다.

1. 리스트 초기화 :
   • m으로 나누어지지 않는 정수를 저장할 리스트와 m으로 나누어지는 정수를 저장할 리스트를 초기화합니다.
2. 정수 분류 : 
   • 1부터 n까지의 정수를 순회하면서 m으로 나누어지는지 확인하고, 해당 리스트에 추가합니다.
3. 합 계산 :
   • 각 리스트의 정수 합을 계산합니다.
4. 결과 반환 :
   • 두 합의 차이를 반환합니다.

시간 및 공간 복잡도 :

1. 시간 복잡도 :
   • O(n) : 1부터 n까지의 정수를 순회하면서 리스트에 추가하고, 리스트의 합을 계산하는 작업이 각 O(n)입니다. 따라서 전체 시간 복잡도는 O(n)입니다.
2. 공간 복잡도 :
   • O(n) : 두 개의 리스트를 사용하여 최대 n개의 정수를 저장하므로 공간 복잡도는 O(n)입니다.

돌이켜보니 이 코드는 조금 더 개선될 수 있었던 것 같아서 조금 더 손봤습니다 : 

class Solution {
    public int differenceOfSums(int n, int m) {
        int num1 = 0;
        int num2 = 0;

        for (int i = 1; i <= n; i++) {
            if (i % m == 0) {
                num2 += i;
            } else {
                num1 += i;
            }
        }

        return num1 - num2;
    }
}

 

사실상 리스트 없이 바로 했어도 문제는 없더군요. 다음에도 이런 실수 조심해야겠습니다.

---

 

개선 되기 전 후 코드 Runtime 결과