[백준/자바] 10986 - 나머지 합

❌ 틀린 답안 : 시간 초과 ❌

  

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        long[] sumArr = new long[(int) n];
        st = new StringTokenizer(br.readLine());

        for(int i=0; i<n; i++) {
            int num = Integer.parseInt(st.nextToken());

            if(i == 0) sumArr[i] = num;
            else sumArr[i] = sumArr[i-1] + num;
        }

        int result = 0;

        for(int i=0; i<n; i++) {
            sumArr[i] %= m;
            if(sumArr[i] == 0) result++;
            if(i > 0) {
                for(int j=i - 1; j>=0; j--) {
                    if(sumArr[j] == sumArr[i]) result++;
                }
            }
        }

        System.out.println(result);
        br.close();
    }
}

---

✅ 통과한 답안 ✅

  

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        long[] sumArr = new long[(int) n];
        long[] remainder = new long[m];

        st = new StringTokenizer(br.readLine());
        sumArr[0] = Integer.parseInt(st.nextToken());
        for(int i=1; i<n; i++) {
            sumArr[i] = sumArr[i - 1] + Integer.parseInt(st.nextToken());
        }

        long result = 0;

        for(int i=0; i<n; i++) {
            sumArr[i] %= m;
            if(sumArr[i] == 0) result++;
            remainder[(int) sumArr[i]]++;
        }

        for(int i=0; i<m; i++) {
            if(remainder[i] > 1)
                result += (remainder[i] * (remainder[i] - 1) / 2);
        }

        System.out.println(result);
        br.close();
    }
}

---

✅ 다른 분 풀이 참고한 답안 ✅

  

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

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

        int[] sumArr = new int[n + 1];
        long[] remainder = new long[m];

        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++) {
            sumArr[i] = (sumArr[i - 1] + Integer.parseInt(st.nextToken())) % m;
            remainder[sumArr[i]]++;
        }

        long result = remainder[0];
        for(int i=0; i<m; i++) {
            if(remainder[i] > 1)
                result += (remainder[i] * (remainder[i] - 1) / 2);
        }

        System.out.println(result);
        br.close();
    }
}