[알고리즘] 10986번

오늘 풀어볼 문제는 백준 10986번 문제 "나머지 합" 이다.

이 문제는 골드3 문제이고 나머지 합 구하기 문제이다.

문제

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.
즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)
둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

출력

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

📌첫 번째 도전📌
문제 접근 자체는 (A + B) % C는 ((A % C) + (B % C)) % C 와 같다는 특징을 이용했다.
즉, 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값이 동일하다는 뜻이다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int N = Integer.parseInt(stringTokenizer.nextToken());
        int M = Integer.parseInt(stringTokenizer.nextToken());

        long[] arr = new long[N+1];
        long[] c = new long[N+1];
        long result = 0;

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for(int i=1; i<=N; i++) {
            arr[i] = arr[i-1] + Integer.parseInt(stringTokenizer.nextToken());
        }

        for(int i=1; i<=N; i++) {
            int remain = (int) arr[i]  % M;
            if(remain == 0) {
                result++;
            }
            c[remain]++;
        }

        for(int i=0; i<M; i++) {
            if(c[i] > 1) {
                result = result + ((c[i] * (c[i] - 1))/2);
            }
        }
        System.out.println(result);
    }
}

문제 자체는 크게 어려운 게 없었다. 하지만 1초 안에 성공을 해야 한다는 점에서 계속 런타임 에러가 발생했다..

첫 도전은 for문 3개로 역할을 나눠 돌려 보았는데, 역시나 런타임 에러였다.
그래서 중복되는 for문을 굳이 역할을 나누지 않고 한 for문으로 묶어서 for문 2개로 최소화 해보았다.

📌두 번째 도전📌

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());

        long[] arr = new long[N+1];
        long[] c = new long[N];
        long result = 0;

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N + 1; i++) {
            arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
            int remain = (int)(arr[i]  % M);
            if(remain == 0) result++;
            c[remain]++;
        }

        for(int i=0; i<M; i++) {
            if(c[i] > 1) {
                result = result + ((c[i] * (c[i] - 1))/2);
            }
        }
        System.out.println(result);
    }
}

하지만 이 또한 런타임 에러였다.. 도대체 왜!!! 얼마나 더 줄여야 하는 걸까?

그래서 속도를 어떻게 더 줄여야 할 지 자신이 없어서 다른 분들이 푼 코드를 보았다.

어떤 블로그를 봤는데 아예 나눈 값 자체를 바로 배열에 넣는 풀이법이 있었다.

📌세 번째 도전📌

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());
        long result = 0;
        long[] S = new long[N + 1];
        long[] cnt = new long[M];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N + 1; i++) {
            S[i] = (S[i - 1] + Integer.parseInt(st.nextToken())) % M;
            if(S[i] == 0) {
                result++;
            }
            cnt[(int) S[i]]++;
        }

        for(int i=0; i<M; i++) {
            if(cnt[i] > 1) {
                result += (cnt[i] * (cnt[i] - 1) / 2);
            }
        }
        System.out.println(result);
    }
}

이렇게 바로바로 입력 받고 나눈 값을 배열에 넣고 하니깐 정답처리가 되었다..

속도... 줄이는 거 너무 어렵다..

[문제 출처] https://www.acmicpc.net/problem/10986