[Codility] GenomicRangeQuery (JavaScript)

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

GenomicRangeQuery coding task - Learn to Code - Codility

 

문제:
유전자 문자열 S와 범위를 정할 배열 P, Q 2개를 받는다. P[i]를 시작 인덱스, Q[i]를 끝 인덱스로 둔다. 문자열 S에서 P[i]~Q[i]에 있는 유전자 중 맵핑된 가장 작은 숫자값을 찾아리턴한다. (S를 이루는 A, C, G, T 는 각각 1, 2, 3, 4로 맵핑되어 있다.)

내 풀이:

function solution(S, P, Q) {
    const nuc = { A:1, C:2, G:3, T:4 };
    const result = [];

    for (let i = 0; i < P.length; i++) {
        const slicedS = S.slice(P[i], Q[i] + 1);
        const mapS = [...new Set(slicedS)].map(v => nuc[v]);
        const min = Math.min.apply(null, mapS);
        result.push(min);
    }
    return result;
}

채점결과: 62%

분석:
정확도 성공, 효율성 실패.
almost_all_same_letters
GGGGGG..??..GGGGGG..??..GGGGGG ✘TIMEOUT ERROR
Killed. Hard limit reached: 7.000 sec.
▶ large_random
large random string, length ✘TIMEOUT ERROR
Killed. Hard limit reached: 7.000 sec.
▶ extreme_large
all max ranges ✘TIMEOUT ERROR
Killed. Hard limit reached: 7.000 sec

원인: 

매 쿼리마다 문자열을 슬라이싱하고 Set/Map/Math.min 실행

• S.slice(P[i], Q[i]+1) → O(N)
• new Set(...) → O(N)
• map(...).Math.min(...) → O(N)

이걸 쿼리마다 하면 총 O(M × N)이 돼서, 최악의 경우 시간 초과
해결법: Prefix Sum 누적합 테이블을 사용한 O(N + M) 풀이

• A, C, G의 등장 횟수를 각각 별도의 누적 배열(prefix sum)로 저장
• 쿼리마다 어떤 문자가 포함되었는지를 O(1)에 판단

수정 풀이:

function solution(S, P, Q) {
    const result = [];
    const N = S.length;
    const A = Array(N + 1).fill(0);
    const C = Array(N + 1).fill(0);
    const G = Array(N + 1).fill(0);

    for (let i = 0; i < N; i++) {
        A[i + 1] = A[i] + Number(S[i] === 'A');
        C[i + 1] = C[i] + Number(S[i] === 'C');
        G[i + 1] = G[i] + Number(S[i] === 'G');
    }
    
    for (let i = 0; i < P.length; i++) {
        const start = P[i];
        const end = Q[i] + 1;

        if (A[start] - A[end]) result.push(1);
        else if (C[start] - C[end]) result.push(2);
        else if (G[start] - G[end]) result.push(3);
        else result.push(4);
    }
    return result;
}

채점결과: 100%