[코딜리티] GenomicRangeQuery (javascript)

 

문제 출처

문제 요약

DNA 서열은 문자 A,C,G,T로 표현 가능하다. 각 문자열은 뉴클레오티드(Nucleotides)유형을 말하고 각각 영향 계수(impact factor)라는 이름의 값으로 1,2,3,4를 갖고 있습니다.

코드로 표현

const  nucleotides = {
  A: 1,
  C: 2,
  G: 3,
  T: 4,
}

P배열과 Q배열은 주어진 문자열(S)인덱스를 말합니다. 예를들어, P[0] = 2 / Q[0] = 4 인 경우는 CAGCCTA 문자열의 2번째 4번째 문자열을 가르키는 것이고, CAGCCTA 그 사이에 존재하는 문자열의 'impact facotr' 값 중에 가장 작은 값을 찾아야 합니다. CAGCCTA 에서 G C C 중 가장 작은 값은 C의 값인 2가 됩니다.

같은 방법으로 P[1] = 5 / Q[1] = 5 인 경우는 CAGCCTA 4가 되고, P[2] = 0 / Q[2] = 6 인 경우는 CAGCCTA 1이 됩니다.

결과값은 [2, 4, 1]

p.s DNA 나 nucleotides 같은 단어가 나오니 일단 어려웠다. 실제 코딩 테스트였으면 해석조차 애먹었을듯 하다.

문제 풀이

첫번째 풀이

const nucleotides = {
  A: 1,
  C: 2,
  G: 3,
  T: 4,
};

function solution(S, P, Q) {
  const result = [];
  P.forEach((_, i) => {
    result.push(
      Math.min(
        ...S.slice(P[i], Q[i] + 1)
          .split("")
          .map((n) => nucleotides[n])
      )
    );
  });
  return result;
}

정확성은 통과했지만 퍼포먼스에서 0점.

forEach문안에서 map ,min 으로 인해서 2중 루프가 된다.

function solution(S, P, Q) {
  const len = S.length + 1;
  const NA = new Array(len).fill(0);
  const NC = new Array(len).fill(0);
  const NG = new Array(len).fill(0);
  const NT = new Array(len).fill(0);

  S.split("").forEach((s, i) => {
    switch (s) {
      case "A":
        NA[i + 1]++;
        break;
      case "C":
        NC[i + 1]++;
        break;
      case "G":
        NG[i + 1]++;
        break;
      case "T":
        NT[i + 1]++;
        break;
      default:
        break;
    }

    NA[i + 1] += NA[i];
    NC[i + 1] += NC[i];
    NG[i + 1] += NG[i];
    NT[i + 1] += NT[i];
  });

  const result = [];
  P.forEach((_, i) => {
    const start = P[i];
    const end = Q[i] + 1;
    if (NA[start] != NA[end]) {
      result.push(1);
    } else if (NC[start] != NC[end]) {
      result.push(2);
    } else if (NG[start] != NG[end]) {
      result.push(3);
    } else {
      result.push(4);
    }
  });

  return result;
}

결론

문자열의 index 에 따른 변화 값을 미리 계산에 해 놓는 다는 발상이 생소하다.

index i 부터 j 내에 특정요소가 존재하는지를 찾을때 응용할 수 있을거 같다.

문자열에 대응하는 계수 값이 상수 이기 때문에 굳이 Math.min 으로 계산할 필요가 없다는 걸 생각하기 어려웠다.

if (NA[start] != NA[end]) {
    result.push(1);
  } else if (NC[start] != NC[end]) {
    result.push(2);
  } else if (NG[start] != NG[end]) {
    result.push(3);
  } else {
    result.push(4);
  }

위 코드처럼 A가 존재하면 최소 값이기 때문에 .