Do-It Algo - 나머지 합 구하기

본 포스팅은 Doit! 알고리즘 코딩테스트 자바 편을 기반으로 작성 되었습니다.

1.Intro

오늘은 나머지 합 구하기, 우선 일반적으로 문제를 보자마자. i~j 까지의 각각의 나머지 합을 구하는 문제인 줄알고, 쉽게 풀 수 있을 것 같은데, 문제를 보니 또 내가 생각한 문제는 아니었던것 같다. 

 

2.Question 

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

3.input

1번 줄에 N과 M(1<= N <=10^6, 2<=M <=10^3)

2번 줄에 N개의 수 A1,A2, A3가 주어진다 (0<=Ai<=10^9)

 

 어..음,, 내가 생각했던 거랑 방향이 좀 다른 것 같다. 일단 나머지의 합을 구하는 문제가 아니었던 것에 놀랐고, 물론 유사하지만, 만약에 작은 배열에서는 쉽게 구할 수 있다지만, 큰 배열에서는 단순한 코딩으로 풀기 어려울 것 같다는 생각에 쉽게 머리가 굴러가지 않았다. 

 

흠,, 조금 더 살펴 보자 

4. Step1. 문제 분석하기 

교재에서 소개 하는 해당 문제의 키 포인드는 다음과 같다

 *   1. (A+B)%C = ((A % C) + (B % C)) % C
	 *     => 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값 = 구간합의 나머지 연산 한 값 동일  
	 *     -?? 이 부분이 잘 이해가 되지 않지만,, 일단 PASS
	 *   2. 구간합 배열을 이용한 식 S[j] - S[i]는 원본 배열의 i+1 ~ j까지의 구간합이다.
	 *   3. S[j] % M = S[i] % M 이라면, (S[j]-S[i]) % M = 0 이다.
	 *    => 즉 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트 하고 S[j]와 S[i]가 같은 (i, j) 쌍을 찾으면 
	 *    원본 배열에서 i+1 ~ j 까지의 구간합이 M 으로 나누어 떨어진 다는 것을 알 수 있다.

그렇다면,, 나머지가 0이 아니어도 동일한 값이 아니더라도 상관이 없다는 걸까,,? 라는 의문이 살짝 든다. 

		1. 배열은 선언 받고, 
	 *    2. 그 배열에 대한 합배열을 생성하고 
	 *    3. 원소값이 0인 개수만 세어 정답
	 *    4. 변경 된 합 배열에서 원소 값이 같은 인덱스의 개수, 즉,나머지 값이 같은 합배열의 개수를 세기 
	 *    0이 3개, 1이 2개이라면 3C2, 2C2로 경우의 수글 구하여 더하기

우선 실행 순서는 다음과 같을 것으로 보인다. 

 

5.Step2. 수도코드 작성

그럼 어제 습관의 필요성을 느낀 수도코드를 작성해보자 

 	 *    int len = 배열크기 입력 받기 
	 *    int target = 나눌 수 입력 받기 
	 *    int sumArr = 합배열 선언 
	 *    int garbegeArr = 나머지 배열 선언 
	 *    
	 *    for(len 만큼 반복) {
	 *    	사용자의 입력값에 맞춰 배열에 정의 
	 *    }
	 *    for(len 1~le) {
	 *    	합배열 S[i] = S[i-1] +A[i];
	 *    }
	 *    
	 *    for( i -> 0~len){
	 *    	remainder = S[i] % M ;
	 *    if(reaminder == 0 ) => 정답 1 증가 
	 *    C[remainder]의 값 1 증가???  // 이건 잘 이해 안됌 
	 *    }
	 *    
	 *    for( i ->0~N{
	 *    	C[i] 에서 2가지를 뽑는 경우의 수를 정답에 더하기? 
	 *    	공식 , C[i]개 중 2ㅐ글 ㄹ뽄느 경우의 수 계산 공식 C[i](C[i]-1)/2
	 *    }
	 * 	  결과 출력

내가 작성한 수도코드는 이렇다.. 물론 공식 같은 것은 교재를 많이참고하긴 했지만,,ㅎ

 

6.step.Final  코드 작성하기 

public static int garbegeSum(int N, int M) {
		// 기본 세팅 영역
        Scanner sc = new Scanner(System.in);
		int answer =0;
		int len = N;
		int target = M;
		long[] sumArr = new long[len];
		long[] garbegeArr = new long[len];
		
		// 구간합 정의 구간 
		sumArr[0] = sc.nextInt();
		for(int i=1; i <len; i++) {
			sumArr[i] = sumArr[i-1] + sc.nextInt();
		}		
       	 //나머지 배열 선언
		for(int i=0; i< len; i++) {
			int remainder = (int)sumArr[i] % target;
			//나머지가 동일한 인덱스의 개수 카운팅 = > remainder == index, 
			if(remainder == 0) answer++;
			garbegeArr[remainder]++;	
		}
        
        	//결과 값 구하기 
		for(int i=0; i<target; i++) {
			if(garbegeArr[i] > 1) {
				answer = (int) (answer + (garbegeArr[i] * (garbegeArr[i]-1) /2));
			}
		}
		return answer;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int len  = sc.nextInt();
		int target = sc.nextInt();
		
		System.out.println(garbegeSum(len, target));
	}

 

어제는 Buffer Reader를 사용했는데, 오늘은 스캐너를 사용해보았다. 

String tokenizer도 계속 해서 사용하다 보니 꽤나 유용한것 같다. 

 

7.Outro

아무튼, 이런 수열 계산,, 고 1때 배운 조합이라던가,, 오랜만에 보는 수학적 개념도 있었는데,, 아직까진 머리가 지끈지끈하다. 

그래도 지속적으로 꾸준히 하다보면 나중엔 쉽게 연상할 수 있지 않을까 생각해보면서 오늘의 알고리즘은 마무리한다.