[Codility - Counting Elements] GenomicRangeQuery

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

GenomicRangeQuery coding task - Learn to Code - Codility

 

- N은 100,000이하, M은 50,000 이하이다. 따라서, O(MN)등의 시간복잡도가 나오면 시간 초과가 난다.

 

- 처음엔 부분 문자열을 추출한 후 binarySearch를 쓸 생각이었는데, 이걸 위해선 먼저 오름차순 정렬을 해야하므로, 그 과정의 시간복잡도가 O(NlogN)이 되버리기 때문에 불가능하다고 판단했다.

 

function solution(S, P, Q) {
    const answer = []
    for(let i = 0; i < P.length; i++){
        let tempString = S.slice(P[i], Q[i]+1)
        if(tempString.indexOf('A') !== -1) answer.push(1)
        else if(tempString.indexOf('C') !== -1) answer.push(2)
        else if(tempString.indexOf('G') !== -1) answer.push(3)
        else answer.push(4)
    }
    return answer
}

 

- 그래서, 직관적으로 쿼리에 해당하는 문자열 부분을 slice해서 추출하고, A부터 시작하여 탐색(indexOf)을 이어나간 뒤, 존재하는 알파벳의 impact 값을 result 배열에 push 해 준다. 그런데 indexOf 메서드가 O(N)이라면 전체 시간복잡도가 O(MN)이 되어 당연히 시간초과가 떠야되는데 뜨질 않는다. 아마 indexOf 메서드가 항상 최악의 경우의 수가 나오지 않아서 인 것 같다. 아니면 codility가 test case를 제대로 만들지 않은 것인지..

 

 

코딜리티(Codility) - GenomicRangeQuery

 

- 그래서 O(M+N) 방식으로 해결하기 위한 알고리즘이 있는데, 각 알파벳마다 array를 두어 각 index마다 현재까지 등장한 횟수를 저장하고, 각 query에 해당하는 index 범위에 맞춰서 해당 알파벳이 존재하는지 여부를 체크하는 방법이다. 이 방법이 아마 정석인 것 같다.