yeonho12345   1년 전

도와주세요 시간초과.....................................................

dontakeman   11달 전

일단 난이도가 골드이고 '누적합' 섹션에 있는 문제니까 단순히 두개의 루프를 사용하는 bruteforce 솔루션이 출제자가 의도한 정답이 아니라는 점을 인정하고 시작해야할 것 같습니다. 

현재 님 코드의 시간 복잡도는 O(N^2) 이죠? 당연히 시간 초과 납니다. 이걸 O(N)으로 줄이셔야 합니다. 조금 정수론적인 지식이 있으면 수월하게 풀리는데 문제의 예시를 사용해보면

1 2 3 1 2 의 누적합은

1 3 6 7 9 죠. 어떤 구간 [l, r] 에 대하여 이 구간의 합은 다음과 같이 나타낼 수 있습니다 - rangeSum([l, r]) = rangeSum([0, r]) - rangeSum([l0, l-1]) 

즉, 이 문제는 구간의 합의 차가 m으로 나누어 떨어지는 경우의 수를 모두 찾는것과 같습니다. 

위의 예시에서 m=3의 경우 다음과 같이 생각해볼 수 있습니다

1. 구간합을 m으로 나눈 나머지가 0

여기에 해당하는 집합은 3, 6, 9 입니다

2. 나머지가 1

여기에 해당하는 집합은 1과 7 입니다

3. 나머지가 2

여기에 해당하는 수는 없습니다

따라서 두 구간의 합의 차가 0이 되게 하려면 나머지가 0인 케이스에서 2개, 1인 케이스에서 2개, 2인 케이스에서 2개를 뽑는 경우를 더한 값과 같습니다. 

하나 주의해야할 점은 나머지가 0인 경우는 두 간이 아니라 하나만 가지고도 성립합니다. 즉, 구간합 9 의 경우 이 구간은 전체 array 가 되는것이죠. 

그렇기에 위의 예시는 

1. 1 2 3 1 2 의 누적합 배열 구하기

2. 각 아이템을 m으로 나눈 나머지에 따라 카운팅 분류 {0: 3, 1: 2, 2: 0}

=> 나머지가 0인 경우는 하나의 구간을 뽑는 것으로도 성립 하므로 더미 데이터 하나를 추가함  {0: 3+1, 1: 2, 2: 0}

3. 각 경우에서 2개씩 뽑기 (4C2 + 2C2+ 0) => 7

댓글을 작성하려면 로그인해야 합니다.