[10986] 나머지 합

링크 : https://www.acmicpc.net/problem/10986

1. 문제 분석

접근 방식: [1,2,3,1,2]에서 1 1 2 1 2 3 1 2 3 1 1 2 3 1 2 이런식으로 코드를 구상, 최대 입력 값이 $10^6$ 이기에 문제에 나와 있는 제한 "1초" 제한 시간을 넘길 것 같았음

이 문제를 풀기 위해 알아둬야 하는건 "나머지 연산의 분배 법칙과 누적 합이다"

(A+B) % C == ((A%C)+(B%C)) % C

원본 : A = [4,6,1,3,2]

누적 합 : P = [4,10,11,14,16]

P[2]=A[0]+A[1]+A[2]

P[0]=A[0]

P[2]-P[0]=A[1]+A[2] 와 같은 것을 알 수 있다.

자, 그렇다면 m이 3일 때 나머지가 어떻게 되는지 확인해보자

원본 배열 -> 나머지 : $R_1$ = [1,0,1,0,2]

누적 합 -> 나머지 : $R_2$ = [1,1,2,2,1]

$R_2[2]$ =2 , $R_2[3]$ =2 라는 걸 확인 할 수 있는데, => P[2] == A[0]+A[1]+A[2] = 4+6+1, P[3] == A[0]+A[1]+A[2]+A[3] = 4+6+1+3

$R_2[1]$ =1 , $R_2[4]$ =1 => P[1] == A[0]+A[1]=4+6, P[4] == A[0]+A[1]+A[2]+A[3] = 4+6+1+3+2

두 지점의 누적 합 나머지가 같다면, m으로 나누어 떨어지는 것을 확인할 수 있다.

나머지가 1인 그룹 : $\binom{3}{2}$

나머지가 2인 그룹 : $\binom{2}{2}$

시간 복잡도: O(N+M)$

2. Python 풀이

import sys
input = sys.stdin.readline
n,m = map(int,input().split())

A=list(map(int,input().split()))

mod_count=[0]*m
curr_pre_sum=0
ans=0

for i in A:
    curr_pre_sum=(curr_pre_sum+i)%m
    if curr_pre_sum==0:
        ans+=1
    mod_count[curr_pre_sum]+=1
   
for count in mod_count:
    if count>1:
        ans+=(count*(count-1))//2

print(ans)

3. 학습 내용

새로 알게 된 점: 나머지 연산, 누적 합 나머지, 조합 python 구현

좀 더 빠른 호율을 가진 코드는 Leetcode에 똑같은 문제를 풀면서 확인했다. Leetcode Problem

Python의 HashMap 개념인데 HashMap에 대해서 공부하고 올릴 예정이다.

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        hmap={0:1}
        res=0
        prefix=0
        for num in nums:
            prefix+=num
            rem=prefix%k
            hmap[rem]=hmap.get(rem,0)+1
        for n in hmap.values():
            res+=n*(n-1)//2
        return res        

공간 효율성: 만약 $K$ 가 $10^9$ 처럼 매우 큰 숫자라면, 리스트로 [0] * K를 만들 경우 메모리 초과(Memory Limit Exceeded)가 발생 => Hash Map은 실제로 등장한 나머지만 저장하므로 메모리를 효율적으로 사용 가능.

1. 문제 분석​

2. Python 풀이​

3. 학습 내용​

4. 관련 개념​

1. 문제 분석

2. Python 풀이

3. 학습 내용

4. 관련 개념