[Codility] GenomicRangeQuery - JavaScript

Sohyeon Bak·2021년 12월 3일

Codility

목록 보기

8/19

문제

A DNA sequence can be represented as a string consisting of the letters A, C, G and T, which correspond to the types of successive nucleotides in the sequence. Each nucleotide has an impact factor, which is an integer. Nucleotides of types A, C, G and T have impact factors of 1, 2, 3 and 4, respectively. You are going to answer several queries of the form: What is the minimal impact factor of nucleotides contained in a particular part of the given DNA sequence?

The DNA sequence is given as a non-empty string S = S[0]S[1]...S[N-1] consisting of N characters. There are M queries, which are given in non-empty arrays P and Q, each consisting of M integers. The K-th query (0 ≤ K < M) requires you to find the minimal impact factor of nucleotides contained in the DNA sequence between positions P[K] and QK.

For example, consider string S = CAGCCTA and arrays P, Q such that:

P[0] = 2    Q[0] = 4
P[1] = 5    Q[1] = 5
P[2] = 0    Q[2] = 6

The answers to these M = 3 queries are as follows:

The part of the DNA between positions 2 and 4 contains nucleotides G and C (twice), whose impact factors are 3 and 2 respectively, so the answer is 2.
The part between positions 5 and 5 contains a single nucleotide T, whose impact factor is 4, so the answer is 4.
The part between positions 0 and 6 (the whole string) contains all nucleotides, in particular nucleotide A whose impact factor is 1, so the answer is 1.
Write a function:

function solution(S, P, Q);

that, given a non-empty string S consisting of N characters and two non-empty arrays P and Q consisting of M integers, returns an array consisting of M integers specifying the consecutive answers to all queries.

Result array should be returned as an array of integers.

For example, given the string S = CAGCCTA and arrays P, Q such that:

P[0] = 2    Q[0] = 4
P[1] = 5    Q[1] = 5
P[2] = 0    Q[2] = 6

the function should return the values [2, 4, 1], as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];
M is an integer within the range [1..50,000];
each element of arrays P and Q is an integer within the range [0..N − 1];
P[K] ≤ Q[K], where 0 ≤ K < M;
string S consists only of upper-case English letters A, C, G, T.

문제해석

가장 작은 impact factors를 찾는 문제이다. S 문자열은 'A', 'C', 'G', 'T' 문자들로 구성되어있다. 'A', 'C', 'G', 'T'는 순서대로 1, 2, 3, 4의 값을 가진다. 그리고 P와 Q 두개의 배열이 주어지는데, 요소들은 S문자열 안에 인덱스를 찾을 수 있는 요소로 구성되어있다. 즉 S문자열의 P[0]부터 Q[0]까지 해당하는 요소를 찾을 수 있다.

S = CAGCCTA
P[0] = 2 Q[0] = 4
P[1] = 5 Q[1] = 5
P[2] = 0 Q[2] = 6

이렇게 주어진다면 S문자열의 2번 인덱스부터 4번 인덱스까지 해당하는 글자는 'GCC'가 해당되고 impact factors의 가장 작은 값은 C임으로 2가 해당되는 것이다.
이렇게 배열 P와 Q로 주어진 인덱스를 기준으로 가장 작은 impact factors를 찾아 배열에 넣어 리턴해야하는 문제이다.

문제풀이

P와 Q의 길이는 동일함으로 둘 중 하나를 기준으로 해 반복문을 사용하여 P[i]-Q[i]까지의 요소를 만들어 그 요소의 'A', 'C', 'G', 'T'를 찾아 해당하는 수를 넣어준다.

P를 기준으로 반복문을 실행하고 slice를 이용해 P[i]부터 Q[i]+1까지의 값을 만든다.
효율성을 위해 if - else if문을 이용해 A부터 T까지 해당하는 요소가 있다면 배열에 넣어준다.

코드

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

    for(let i = 0; i<P.length; i++){
        let min = Infinity;
        for(let j = P[i]; j<=Q[i]; j++){
            min = Math.min(IFactor.indexOf(S[j])+1, min)
        }
        answer.push(min)
    }

    return answer
}