HR - Subarray Division

Goody·2021년 2월 4일
0

알고리즘

목록 보기
28/122

문제

Given a chocolate bar, two children, Lily and Ron, are determining how to share it. Each of the squares has an integer on it.

Lily decides to share a contiguous segment of the bar selected such that:

  • The length of the segment matches Ron's birth month, and,
  • The sum of the integers on the squares is equal to his birth day.

You must determine how many ways she can divide the chocolate.

예시

INPUT_1

5
1 2 1 3 2
3 2

OUTPUT_1

2

Explanation_1
Lily wants to give Ron m = 2 squares summing to d = 3. The following two segments meet the criteria:

INPUT_2

6
1 1 1 1 1 1
3 2

OUTPUT_2

0

Explanation_2
Lily only wants to give Ron m = 2 consecutive squares of chocolate whose integers sum to d = 3 . There are no possible pieces satisfying these constraints:

Thus, we print 0 as our answer.

풀이

  • s 배열 내 인접한 m 개의 수의 합이 d 가 될 수 있는 경우의 수를 구하는 문제이다.
  • 0부터 m 까지 커지는 루프를 돌면서 s 배열 내 원소끼리 더한 값을 sum 에 계속 저장한다.
  • 이후 s 배열의 맨 앞칸을 shift 로 지운다.
  • 더한 sum 의 값이 d와 같다면 count 를 하나 늘린다.
  • 위 과정을 배열 s 의 길이가 0보다 클 동안 반복한다.

코드

function birthday(s, d, m) {
    let count = 0;

    while(s.length > 0) {

        let sum = 0;
        for(let i = 0; i < m; i++) {
            sum += s[i];
        }
        s.shift();

        if(sum === d) count++;
        
    }
    return count;
}

0개의 댓글