[Hackerrank] Sub-array Division (Easy)

[Hackerrank] Sub-array Division - (Implemetation - Easy)

www.hackerrank.com/challenges/the-birthday-bar/problem

Sub-array Division | HackerRank

---

문제

리스트 s가 주어진다

앞에서부터 순서대로 m 길이만큼 잘라서 더한후 값이 d와 같으면 count를 1 더해준다

그리고 최종적으로 count를 출력해준다

예를들어 1,2,1,3,2이고 m이 2, d가 3이면,

12, 21, 13, 32 경우의 수가 나오고

합한 숫자가 3인 경우가 총 2개이므로 결과는 2이다

해결

2가지 방식으로 풀었다

이중포문으로 풀고 시간복잡도를 O(n)으로 줄였다

1. 이중포문

static int birthday(List<Integer> s, int d, int m) {
    int result = 0;
    for (int i=0; i<s.size(); i++) {
        int sum = 0;
        for (int j=i; j<i+m; j++) {
            if (i+m <= s.size()) sum += s.get(j);
        }
        if (d==sum) result++;
    }
    return result;
}

2. O(n)

static int birthday2(List<Integer> s, int d, int m) {
    int result = 0;
    int sum = 0;
    for (int i = 0; i < s.size(); i++) {
        sum += s.get(i);
        if (i>=m) sum -= s.get(i - m);
        if (i>=m-1 && sum == d) result++;
    }
    return result;
}