[코딩테스트] Codility 5-3 GenomicRangeQuery (JavaScript)

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

 

 

Solution1

정답률 : 62%

시간복잡도 : O(N * M)

 

코드 작성

S를 impact factor 숫자로 된 문자열로 바꾸기

P와 Q를 반복문으로 순회하며, S 구간별 최소값 찾기

 

function solution(S, P, Q) {
    
  let Num = '';
  for (let i=0; i<S.length; i++) {
    if (S[i]==='A') Num += '1';
    if (S[i]==='C') Num += '2';
    if (S[i]==='G') Num += '3';
    if (S[i]==='T') Num += '4';
  }
    
  let result = [];
  let M = P.length;
  for (let i=0; i<M; i++) {
    let min = 4;
    let p = P[i];
    let q = Q[i];

    for (let j=p; j<=q; j++) {
      if (min===1) break;
      if (Num[j] <min) min=Num[j];
    }
    result.push(Number(min))
  }
  
  return result;
}

 

리뷰

Correctness tests : 통과

Performance tests : 실패

시간복잡도 : O(N*M)

 

 

Solution2

정답률 : 100%
시간복잡도 : O(N+M)

 

코드 작성

function solution (S, P, Q) {
  let part = '';
  let result = [];

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

    if (part.indexOf('A') !== -1) {
      result.push(1)
    } else if (part.indexOf('C') !== -1) {
      result.push(2)
    } else if (part.indexOf('G') !== -1) {
      result.push(3)
    } else {
      result.push(4)
    }
  }
  
  return result;
}

 

리뷰

정답률 : 100%
시간복잡도 : O(N+M)

 

반복문 내에 slice를 사용해서 시간복잡도가 O(N^2)가 나올 줄 알았는데 그렇지 않았다.

문자열 메소드의 경우 시간복잡도가 낮게 측정되는지 확인해봐야겠다.