코딩 테스트 [자료구조] - 나머지 합 구하기

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

---

입력

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

출력

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

예제 입력
5 3
1 2 3 1 2

예제 출력
7

---

1단계 - 문제 분석하기

106개의 수에 대하여 모든 구간의 합을 구해야 하기 때문에 1초안에 연산하기는 어렵다. 그러므로 구간 합 배열을 이용한다.

나머지 합 문제 풀이의 핵심 아이디어

• (A + B) % C는 ((A % C) + (B % C)) % C 와 같다. 다시 말해 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일하다.
• 구간 합 배열을 이용한 식 S[j] - S[i]는 원본 배열의 i+1 부터 j까지의 구간 합이다.
• S[j] % M의 값과 S[i] % M의 값이 같다면 (S[j] - S[i]) % M은 0이다.
즉, 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트하고 S[j]와 S[i]가 같은 (i, j)쌍을 찾으면 원본 배열에서 i + 1부터 j까지의 구간 합이 M으로 나누어떨어진다는 것을 알 수 있다.

2단계 - 손으로 풀어 보기

1 A배열의 합 배열 S를 생성한다.

2 합 배열 S의 모든 값을 M으로 나머지 연산을 수행해 값을 업데이트한다.

3 변경된 합 배열에서 원소 값이 0인 개수만 세어 정답에 더한다.

경우의 수 += 3

4 변경된 합 배열에서 원소 값이 같은 인덱스(나머지 값이 같은 인덱스)의 개수를 센다.

0이 3개, 1이 2개이므로 3C2, 2C2

3C2 = 3

2C2 = 1

총 경우의 수 = 3 + 3 + 1 = 7

3단계 - sudo코드 작성하기

N 입력받기 (수열의 개수)
M 입력받기 (나누어떨어져야 하는 수)
S 선언하기 (합 배열)
C 선언하기 (같은 나머지의 인덱스를 카운트하는 배열)

for(i -> 1 ~ N) {
	S[i] = S[i -1] + A[i]	// 합 배열 저장
}

for(i -> 0 ~ N) {
	remainder = S[i] % M	// 합 배열을 M으로 나눈 나머지 값
    
    if(remainder == 0)
    	정답을 1 증가
        
    C[remainder]의 값을 1 증가
}

for(i -> 0 ~ M) {
	C[i]에서 2가지를 뽑는 경우의 수를 정답에 더하기
    // C[i]개 중 2개를 뽑는 경우의 수 계산 공식 C[i] * (C[i]-1) / 2
}

4단계 - 코드 구현하기

import java.util.Scanner;

public class Q5 {
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        long[] S = new long[N];
        long[] C = new long[M];
        long answer = 0;

        S[0] = sc.nextInt();
        for(int i = 1; i < N; i++){
            S[i] = S[i-1] + sc.nextInt();
        }

        for(int i = 0; i < N; i++){
            int remainder = (int) (S[i] % M);
            if(remainder == 0)
                answer += 1;
            C[remainder] += 1;
        }

        for(int i = 0; i < M; i++){
            if(C[i] > 1){
                answer = answer + (C[i] * (C[i]-1) / 2);
            }
        }

        System.out.println(answer);
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편