[Javascript] Codility Lesson 5 - GenomicRangeQuery

문제: https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/

 

문제 요약:

• A,C,G,T로 이루어진 문자열 S가 주어지며 각 문자는 순서대로 1,2,3,4 값을 갖는다. (A=1, C=2, G=3, T=4)
• 문자열 S의 길이 범위는 [1... 100000] 이다.
• 동일한 길이의 배열 P,Q가 주어지며, 배열의 요소 범위는 [0... N - 1] 이다.
• 배열 P,Q의 길이 범위는  [1... 50000] 이다.
• P[i] <= Q[i] 이다.

function solution(S, P, Q) {
    let result = [];
    let impact = ['A', 'C', 'G', 'T'];

    for (let i = 0; i < P.length; i++) {
        let tmpS = S.slice(P[i], Q[i] + 1);

        for (let j = 0; j < impact.length; j++) {            
            if (tmpS.indexOf(impact[j]) !== -1) {
                result.push(j + 1);
                break;
            };
        };
    };

    return result;
}

https://app.codility.com

이중 for문임에도 불구하고 시간 복잡도는 O(N+M)로 나왔다. 이유는 impact 배열의 길이가 4로 고정되어 있기 때문이다. 

 

 

이중 for문에서 배열의 길이가 고정된 경우 시간복잡도 

• https://stackoverflow.com/questions/16204754/what-is-the-big-o-notation-of-a-nested-loop-where-the-inner-loop-is-ran-a-fixed
• https://www.quora.com/For-a-for-loop-nested-inside-another-for-loop-is-the-time-complexity-always-of-O-n-2-If-not-please-give-examples-of-some-cases-that-violate-this