[Codility] Lesson 5: Prefix Sums - GenomicRangeQuery (javascript)

깃허브 : https://github.com/miiingo/codility

Task description

원본 사이트 : https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/

GenomicRangeQuery coding task - Learn to Code - Codility

- N 문자로 구성된 비어 있지 않은 문자열 S와 M 개의 정수로 구성된 비어 있지 않은 두 개의 배열 P, Q가 주어지면 모든 쿼리에 대한 연속 응답을 지정하는 M 개의 정수로 구성된 배열을 return
- 가장 효율적인 알고리즘 작성
- N은 [1..100,000] 범위 내의 정수
- M은 [1..50,000] 범위 내의 정수
- 배열 P, Q의 각 요소는 [0..N - 1][0..N - 1] 범위 내의 정수
- 0 ≤ K < M일 경우, P[K] ≤ Q[K]
- 문자열 S는 대문자 영문 A, C, G, T로만 구성

 

Solution

CASE 1: 해당 문자열을 Set에 넣고 최소값 계산 - 62%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(S, P, Q) {
    // write your code in JavaScript (Node.js 8.9.4)
    let result = [];
    
    for(let K in P) {
        const query = S.substring(P[K], Q[K]+1);
        const queryArr = query.split('');
        const querySet = new Set(queryArr);
        if(querySet.has('A')){
            result[K] = 1;
        }
        else if(querySet.has('C')){
            result[K] = 2;
        }
        else if(querySet.has('G')){
            result[K] = 3;
        }
        else if(querySet.has('T')){
            result[K] = 4;
        }
    }
    
    return result;
}

- result : 결과 값을 저장하는 배열
- query : P[K]와 Q[K] 사이의 문자열
- queryArr : query 문자열을 배열로 바꾼 값
- querySet : queryArr 배열을 Set 객체에 넣은 값
- querySet 객체가 'A'를 가지고 있으면 최소 값은 1, 'C'를 가지고 있으면 최소 값은 2, 'G'를 가지고 있으면 최소 값은 3, 'T'를 가지고 있으면 최소 값은 4로 설정
- result 배열을 return

 

CASE 1: Result

 

CASE 1: Analysis

The following issues have been detected: timeout errors.
다음과 같은 문제가 감지되었습니다. 시간 초과 오류.

CASE 1: 분석

정확성은 좋지만, 효율성 측면에서 좋지 않음

 

CASE 2: 인덱스 값까지의 문자 개수로 비교 - 62%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(S, P, Q) {
    // write your code in JavaScript (Node.js 8.9.4)
    const array = S.split('');
    const N = array.length;
    let A = new Array(N+1).fill(0);
    let C = new Array(N+1).fill(0);
    let G = new Array(N+1).fill(0);
    let result = [];
    
    for(let i=0; i<N; i++) {
        switch(array[i]){
            case 'A':
                A[i+1]++;
                break;
            case 'C':
                C[i+1]++;
                break;
            case 'G':
                G[i+1]++;
                break;
            default:
                break;
        }
        A[i+1] += A[i];
        C[i+1] += C[i];
        G[i+1] += G[i];
    }

    for(let i in P){
        if(A[P[i]+1] != A[Q[i]+1]){
            result[i] = 1;
        }
        else if(C[P[i]+1] != C[Q[i]+1]){
            result[i] = 2;
        }
        else if(G[P[i]+1] != G[Q[i]+1]){
            result[i] = 3;
        }
        else{
            result[i] = 4;
        }
    }
    
    return result;
}

- array : 문자열 S를 배열로 변환한 값
- N : array의 길이 (문자열 S의 길이)
- A : array에서 해당 인덱스값까지 A 문자가 나온 횟수
- C : array에서 해당 인덱스값까지 C 문자가 나온 횟수
- G : array에서 해당 인덱스값까지 G 문자가 나온 횟수
- A, C, G에 해당하지 않는 나머지 경우는 T이므로 T에 대한 배열은 따로 구성 X
- 이전 값과의 비교가 필요하므로 배열 A, C, G의 길이는 N+1로 설정
- array에 대해 for문을 돌며 A, C, G 문자가 나온 횟수를 각각 A, C, G 배열에 저장
- P[i]+1과 Q[i]+1 인덱스에 대한 각 A, C, G 배열의 값이 다를 경우, 해당 문자가 있었다는 이야기이므로 해당 값을 result[i]에 저장 (최소값을 저장해야하기 때문에 A, C, G 순서로 확인)

 

CASE 2: Result

 

CASE 2: Analysis

The following issues have been detected: wrong answers.
For example, for the input ('A', [0], [0]) the solution returned a wrong answer (got [4] expected [1]).
다음과 같은 문제가 감지되었습니다. 오답.
예를 들어, 입력 ('A', [0], [0])에 대해 솔루션이 잘못된 답변을 반환했습니다 (예상: [1], 결과: [4]).

 

CASE 2: 분석

반대로 효율성은 좋지만, 정확성이 떨어짐
P[i]와 Q[i]의 값이 동일할 경우, 비교하는 A, C, G 배열의 값이 동일하기 때문에 result 값이 제대로 설정되지 않음

 

CASE 3: 인덱스 값까지의 문자 개수로 비교(P[K]와 Q[K] 값이 같을 때의 예외처리 추가) - 75%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(S, P, Q) {
    // write your code in JavaScript (Node.js 8.9.4)
    const array = S.split('');
    const N = array.length;
    let A = new Array(N+1).fill(0);
    let C = new Array(N+1).fill(0);
    let G = new Array(N+1).fill(0);
    let result = [];
    
    for(let i=0; i<N; i++) {
        switch(array[i]){
            case 'A':
                A[i+1]++;
                break;
            case 'C':
                C[i+1]++;
                break;
            case 'G':
                G[i+1]++;
                break;
            default:
                break;
        }
        A[i+1] += A[i];
        C[i+1] += C[i];
        G[i+1] += G[i];
    }

    for(let K in P){
        let start = P[K] + 1;
        let end = Q[K] + 1;
        if(start == end){
            start--;
        }
        
        if(A[start] != A[end]){
            result[K] = 1;
        }
        else if(C[start] != C[end]){
            result[K] = 2;
        }
        else if(G[start] != G[end]){
            result[K] = 3;
        }
        else{
            result[K] = 4;
        }
    }
    
    return result;
}

- 기본적으로 CASE 2와 동일
- P[K]와 Q[K]의 값이 같을 경우에 start 값을 --한 뒤 비교

 

CASE 3: Result

 

CASE 3: Analysis

The following issues have been detected: wrong answers.
For example, for the input ('AC', [0, 0, 1], [0, 1, 1]) the solution returned a wrong answer (got [1, 2, 2] expected [1, 1, 2]).
다음과 같은 문제가 감지되었습니다. 오답.
예를 들어 입력 ( 'AC', [0, 0, 1], [0, 1, 1])의 경우 솔루션에서 잘못된 답변을 반환했습니다 (예상: [1, 1, 2], 결과: [1, 2, 2]).

 

CASE 3: 분석

비교에 대한 start 값이 잘못 설정됨
start 값은 P[K]+1이 아닌 P[K]가 되어야 함
start 값을 P[K]+1로 설정하면 array[K] 문자는 포함하지 않은 상태료 비교하게 됨

 

CASE 4: 인덱스 값까지의 문자 개수로 비교 (오류 수정) - 100%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(S, P, Q) {
    // write your code in JavaScript (Node.js 8.9.4)
    const array = S.split('');
    const N = array.length;
    let A = new Array(N+1).fill(0);
    let C = new Array(N+1).fill(0);
    let G = new Array(N+1).fill(0);
    let result = [];
    
    for(let i=0; i<N; i++) {
        switch(array[i]){
            case 'A':
                A[i+1]++;
                break;
            case 'C':
                C[i+1]++;
                break;
            case 'G':
                G[i+1]++;
                break;
            default:
                break;
        }
        A[i+1] += A[i];
        C[i+1] += C[i];
        G[i+1] += G[i];
    }

    for(let K in P){
        let start = P[K];
        let end = Q[K] + 1;
        
        if(A[start] != A[end]){
            result[K] = 1;
        }
        else if(C[start] != C[end]){
            result[K] = 2;
        }
        else if(G[start] != G[end]){
            result[K] = 3;
        }
        else{
            result[K] = 4;
        }
    }
    
    return result;
}

- 기본적으로 CASE 2과 동일
- result 값을 설정하는 두 번쨰 for문에서 start의 값을 P[K]+1이 아닌 P[K]로 설정

 

CASE 4: Result

 

CASE 4: Analysis

The solution obtained perfect score.
이 솔루션은 완벽한 점수를 얻었습니다.

 

결론

문자열 S에는 A, C, G, T 네 가지의 문자만으로 구성되어 있기 때문에, 효율성을 위해 마지막 순서인 T는 직접 계산하지 않고 A, C, G에 포함되지 않는 경우로 설정

모든 경우의 수를 따져야 하는 경우, 시간복잡도를 고려해야함

효율적인 방법을 위해서는 값의 변화를 배열로 만들어서 비교하는 것이 빠름

단, 비교할 값의 대상을 선정할 때 신중히 고려해야함
  - P[K]~Q[K] 인덱스에 대한 문자열 S의 값을 대상으로 비교
  - 배열 A, C, G는 값의 변화를 체크하기 위해 N+1 길이로 설정됨
  - 따라서 P[K]~Q[K]+1 인덱스에 대한 배열 A, C, G 값을 비교해야 제대로 된 result 값이 나옴