JAVA_나머지 합을 구하는 알고리즘

자바 알고리즘-나머지 합을 구하는 알고리즘

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

 

▶ 나의 문제풀이 

나머지의 합이 M으로 떨어지는 구간의 개수를 구하는 문제입니다.

M으로 떨어지는 구간 2가지를 선택해야 합니다. 
나머지에 대한 누적합을 구하고 그 경우의 수를 더하는 문제입니다.

구간의 합의 나머지가 0이 되는 조건을 살펴보겠습니다. 

 

우선 문제를 풀때 생각한 점을 나열하겠습니다,

 

1. 배열의 길이는 몇자리로 할것인지 System.in으로 입력받기

1-1) N의 배열에 사용자에게 자리수 받기

1-2) M으로 나눌것이니까 사용자에게 몇으로 나눌건지 입력받기

 

2. 합배열을 만들고 들어오는 수를  System.in으로 입력받기
long[] S = new long[N];
// 아까 배열의 개수를 몇개를 지정하겠다고 했으니까!
// 그 값 만큼 배열의 길이를 만들기.

 

3. 합배열을 M으로 나눈 나머지 값 저장
long[] C = new long[M];

즉, 배열 S 에는 각각 System.in한 수를 더해서 저장할것이고,

C 배열에는 합배열을 M으로 나눈 수만큼만 저장할 것.

 

4. 합배열에 0번째에는 첫번째 로 들어온 값을 저장하고,
1번째 배열부터 N번째 까지 돌면서 하나씩 더하고 합배열에 저장하기.

4-1) S[0] = sc.nextInt();

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

 

5. 합배열의 i번째와 M을 계속 나누고 그 나머지 값을 remainder에 저장
for (int i = 0; i < N; i++) {
int remainder = (int) (S[i] % M);
if (remainder == 0) {
C[remainder]++;
} }

위의 for문 안에서 만약,  M으로 나눈수의 나머지가 0이 된다면 딱 떨어져서 나눠진것,

이것을 C 배열의 [0]번째에 저장하고 그 0번째의 값을 계속 증가시켜준다.

 

long answer = 0;

answer 변수 생성!

 

6. C[remainder]가 for문을 끝나게 된다면 C의 배열의 값이 전부 들어가 있을것.

이제 여기서 나머지 수의 경우의 수를 구하면 끝!!!!!!
for (int i = 0; i < M; i++) {

//나머지의 값은 나누는 값보다 클수 없기때문에 M 까지 도는 것!
if (C[i] > 1) {
// 1보다 큰 이유는, 나눴을때 나머지가 0이나 1임을 제외하는것임.
answer = answer + (C[i] * (C[i] - 1) / 2);

//여기서 나머지가 같은 인덱스 중 2개를 뽑는 경우의 수를 고르기 위해서 나누기2를 해주었습니다.
}}
System.out.println(answer);

 

(합배열의 2번째를 M으로 나눈값과 합배열의 3번째를 M으로 나눈 값과 같으냐?

S[2]%M=S[3]%M 이런 방법도 있음.)

 

 

▶ 나의 코드 

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

import java.util.Scanner;

public class 나머지합구하기 {

	public static void main(String[] args) {
		// 입력 받을것!
		Scanner sc = new Scanner(System.in);
		// 배열의 개수 N
		System.out.println("배열 몇자리수?");
		int N = sc.nextInt();

		// 나누어 떨어져야 하는 수 M
		System.out.println("몇으로 나누어 떨어져야하는지?");
		int M = sc.nextInt();

		// 합배열 저장
		long[] S = new long[N];
		// 아까 배열의 개수를 몇개를 지정하겠다고 했으니까!
		// 그 값 만큼 배열의 길이를 만들기.

		// 합배열을 M으로 나눈 나머지 값 저장
		long[] C = new long[M];

		// 합배열 0번째는 그냥 입력한 값 저장
		System.out.println("합배열 0번째 값 입력");
		S[0] = sc.nextInt();

		// 이제 합배열에 0번째에는 첫번째 값이 있으니까
		// 1번째 배열부터 N번째 까지 돌면서 하나씩 합 배열을 만들기!
		for (int i = 1; i < N; i++) {
			S[i] = S[i - 1] + sc.nextInt();
		}

		// 이제 M값으로 나머지 연산을 수행하기!!!
		for (int i = 0; i < N; i++) {
			// 이제 0번째 부터 합배열 길이만큼 전체를 돌면서

			// M으로 나눴을때 나머지가 0이 될때
			int remainder = (int) (S[i] % M);
			if (remainder == 0) {
				// 카운트 배열에 같은 인덱스에 값을 증가시킨다.
				C[remainder]++;
			}
			// 이렇게 하면 같은수가 M으로 나눴을때 0이 된것이 많으면
			// [0]번째 인덱스에 ++되어 값이 저장되게 됩니다.
			// 나머지의 값은 나누는 값보다 클수 없기때문에
			// 다음 for문을 돌릴때 i의 값은 M 보다 클 수 없습니다.
		}
		long answer = 0;

		for (int i = 0; i < M; i++) {
			if (C[i] > 1) {
				// 1보다 큰 이유는, 나눴을때 나머지가 0이나 1임을 제외하는것임.
				answer = answer + (C[i] * (C[i] - 1) / 2);
			}
		}
		System.out.println(answer);
	}
}

 

 

 

 

 

<참고>

책: do it 알고리즘 코딩 테스트 자바편

코딩 테스트:https://www.acmicpc.net/problem/10986

10986번: 나머지 합