Table of contents

코딜리티 GenomicRangeQuery

A(1), C,(2) G(3), T(4)로 이루어진 문자열 S와 배열 P, Q이 주어졌을 때, 배열의 인덱스 p, q를 이용한 S의 substring에서 최소값을 찾는 문제이다.

첫번째 풀이

O(N * M)

private int[] genomicRangeQuery(String S, int[] P, int[] Q) {
    int M = P.length;

    char[] seqs = S.toCharArray();
    int[] result = new int[M];

    for (int i = 0; i < M; i++) {
        int p = P[i];
        int q = Q[i];

        char lastSeq = 'T';
        for (int j = p; j <= q; j++) {
            if (lastSeq > seqs[j]) {
                lastSeq = seqs[j];
            }
        }

        if (lastSeq == 'A') {
            result[i] = 1;
        } else if (lastSeq == 'C') {
            result[i] = 2;
        } else if (lastSeq == 'G') {
            result[i] = 3;
        } else if (lastSeq == 'T') {
            result[i] = 4;
        }
    }

    return result;
}

대부분 비슷한 방식으로 풀었을 거라고 생각한다. S.substring(p, q)에서 가장 작은 값을 갖는 요소룰 찾아서 값을 설정한다. 문자열의 길이 N이 100,000, 배열의 길이 M이 50,000 의 최대값을 갖는 문제에서 O(N * M)의 복잡도를 갖기 때문에 time out 에 걸린다.

두번째 풀이

O(N + M)

우선 구간 합(prefix sum)이 무엇인지 알아야 하는데, 여기를 참조하길 바란다. 어쩃든 두번째 풀이의 원리는 직접 계산하지 않고 문자열 S에서 각 DNA 문자가 등장할 때마다 값을 누적시켜서 해결한다.

private int[] test(String S, int[] P, int[] Q) {
    int N = S.length();
    int M = P.length;

    int[] result = new int[M];

    int[][] path = new int[4][N];
    switch (S.charAt(0)) {
        case 'A':
            path[0][0] = 1;
            break;
        case 'C':
            path[1][0] = 1;
            break;
        case 'G':
            path[2][0] = 1;
            break;
        case 'T':
            path[3][0] = 1;
            break;
    }

    for (int i = 1; i < N; i++) {
        char c = S.charAt(i);

        switch (c) {
            case 'A':
                path[0][i] = path[0][i - 1] + 1;
                path[1][i] = path[1][i - 1];
                path[2][i] = path[2][i - 1];
                path[3][i] = path[3][i - 1];
                break;
            case 'C':
                path[0][i] = path[0][i - 1];
                path[1][i] = path[1][i - 1] + 1;
                path[2][i] = path[2][i - 1];
                path[3][i] = path[3][i - 1];
                break;
            case 'G':
                path[0][i] = path[0][i - 1];
                path[1][i] = path[1][i - 1];
                path[2][i] = path[2][i - 1] + 1;
                path[3][i] = path[3][i - 1];
                break;
            case 'T':
                path[0][i] = path[0][i - 1];
                path[1][i] = path[1][i - 1];
                path[2][i] = path[2][i - 1];
                path[3][i] = path[3][i - 1] + 1;
                break;
        }
    }

    for (int i = 0; i < M; i++) {
        for (int p = 0; p < 4; p++) {
            int sub = 0;
            if (P[i] > 0) {
                sub = path[p][P[i] - 1];
            }

            if (path[p][Q[i]] - sub > 0) {
                result[i] = p + 1;
                break;
            }
        }
    }

    return result;
}

조금 난해한 코드이므로 잘 분석해야 한다.

  1. 누적되는 값은 0부터 시작하여 1씩 증가한다.
    1. 배열 path의 index: A는 0, C는 1, G는 2, T는 3
    2. 처음 switch (S.charAt(0))
      1. 첫번째 DNA 문자에 대한 값을 설정한다.
    3. for (int i = 1; i < N; i++)
      1. 각 DNA 문자가 등장하면 이전 값에 1을 더한 값을 저장한다.
      2. 해당 DNA 문자를 제외한 나머지 문자는 이전 값을 다시 저장한다.

우선 문제에서 주어진 예제를 토대로 분석해보자.

S = CAGCCTA

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

  • A 경로: path[0] = 0 1 1 1 1 1 2
  • C 경로: path[1] = 1 1 1 2 3 3 3
  • G 경로: path[2] = 0 0 1 1 1 1 1
  • T 경로: path[3] = 0 0 0 0 0 1 1

현재 경로는 위와 같이 이전 값을 누적하면서 문자가 등장할 때마다 +1이 증가하여 누적된 모습을 지닌다.

  1. 각 P[i], Q[i] 값에 대해, path[0]부터 시작하여 path[3]까지 검사한다.

  2. P[i] - 1에 해당하는 경로값과, Q[i] 에 해당하는 경로값을 비교하여 최소값을 구할 수 있다.

    1. 만약, 해당 문자의 검사에서 P[i] - 1 이 0보다 작다면, Q[i]가 0보다 큰 경우 해당 문자가 최소값이다.
      1. 작은 문자부터 순서대로 검사하여 최소값을 찾았으므로 다음 문자는 검사하지 않아도 된다.

  3. 만약 0 ~ 1 문자열 즉, CA에서 최소값을 찾는다면 1 (=A)이다.

    1. path[0]: Q[i] = 1이므로 O
    2. 나머진 검사하지 않음

  4. 만약 2 ~ 5 문자열 즉, GCCT에서 최소값을 찾는다면 2 (=C)이다.

    1. path[0]: P[i - 1] = 1, Q[i] = 1 이므로 x
    2. path[1]: P[i - 1] = 1, Q[i] = 3 이므로 O
    3. 나머진 검사하지 않음

마지막 반복문은 위의 내용을 코드로 옮긴 것이다.

정리

이번엔 너무 어려웠다. 처음 풀이부터 바로 이런 해답을 구하는 사람이 있긴 할까 궁금하다. 코드가 이해가 안가는 사람은 codility - GenomicRangeQuery 정답 및 해설 이 포스팅의 코드가 더 직관적이므로 참조하면 좋을 것 같다.