코딜리티(Codility) - GenomicRangeQuery

코딜리티(Codility) - GenomicRangeQuery

☞ 문제링크

문제 설명

주어진 문자열(S)의 각 문자 A,C,G,T는 각각 'impact factor'라는 이름의 값으로 1,2,3,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이 됩니다.

문제 풀이

문제를 해결하는 것은 어렵지 않지만, 시간복잡도를 해결하기가 매우 힘듭니다. (O(N+M)이하가 되어야 효율성에서 100점이 나오는 문제입니다.) 풀이방법의 아이디어는 생각났지만, 구현하는 과정이 너무 생소하여서 쉽게 풀지 못했습니다. 해당 풀이방법은 기억해두면 비슷한 문제를 해결할때 도움이 될 것 같습니다. 풀이 방법의 절차는 아래와 같습니다.

1. 문자는 A,C,G,T로 4가지 경우만 존재합니다. 해당 문자가 특정 인덱스를 기준으로 추가가 되었는지 안되었는지 기록하기 위해서 별도의 배열을 만듭니다.  이 부분이 핵심입니다.

   public int[] solution(String S, int[] P, int[] Q) {
       int[] A = new int[S.length() + 1];
       int[] C = new int[S.length() + 1];
       int[] G = new int[S.length() + 1];
         . . .
   

   첫번째 인덱스부터 기록을 해야 하기 때문에 문자열보다 하나 큰 길이의 배열을 선언합니다. (T의 추가여부를 기록하는 배열도 원래 필요하지만 사실 나머지 3가지만 알면 되기 때문에, 굳이 선언하지 않았습니다.) 이유는 아래에서 설명하겠습니다.
2. 이제 주어진 문자열(S)를 하나씩 검사하면서, 변화를 기록합니다. 

    . . . (생략) . . .
   char[] chars = S.toCharArray();
   for (int i = 0; i < chars.length; i++) {
       switch (chars[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];
   }
      . . .
   

   모두 기록하게 되면 배열들의 인덱스는 예제로 표현하면 다음과 같습니다.(S = CAGCCTA)

   A = {0, 0, 1, 1, 1, 1, 2} // A에 같은 경우 1번째 인덱스의 하나가 추가 되었기 때문에, A배열 2번째에 1을 추가했습니다. 그리고 6번째 인덱스에 하나 추가가 되었기 때문에, A배열 7번째 인덱스에 다시 1을 추가했습니다. 인덱스가 하나 다른 이유는 첫번째 인덱스부터 변화를 감지하기 위함입니다. 같은 방식으로 C와 G의 변화도 감지합니다.
   C = {0, 1, 1, 2, 3, 3, 3}
   G = {0, 0, 1, 1, 1, 1, 1}
   

3. 이제 P와 Q의 값을 이용하여서 해당 인덱스 내의 변화 여부를 A부터 C, G, T 순으로 확인합니다. (작은값부터 확인) 만약 변화가 되었다면, 해당 값을 저장합니다. 예를들어,  P[0] = 2 / Q[0] = 4 인 경우는 2~4번째 인덱스의 변화를 확인합니다. A배열의 2번째 인덱스와 5번쨰 인덱스를 비교하면 둘 다 1로 똑같습니다. A가 해당 인덱스 동안 추가되지 않았다는 것을 알 수 있습니다. A가 추가 되지 않았으면 C, G, T 순서로 확인합니다. (A,C,G에서 모두 변화가 없다면 T만 변화한걸로 확인하면 되기 때문에 T배열은 굳이 필요가 없습니다.)

☞ 해당 Github 문제풀이 링크

배운점

• 해당 문제 풀이 방법이 낯설었는데, 새로운 방식을 알게 되었다! 비슷한 문제에 어려움이 없도록 풀이 방식을 기억해둬야 한다.
• 'impact factor'이라는 단어를 해석할려다가 애먹었는데, 그냥 대명사처럼 쓰이는 용어였다. 이탤릭체로 써서 힌트를 줬었는데, 이를 캐치해내지 못했다. 다음부턴 이탤릭체를 좀 더 유심히 보고, 이탤릭체가 아니더라도 대명사 처럼 쓰이는 용어가 있는지 잘 확인해야 겠다.