Lesson 5 - GenomicRangeQuery

자세한 문제는 여기를 확인해 주셔요

 

간략하자면 S의 문자열에서 P[N] 값과 Q[N] 값의 문자열 중 작은 값을 반환하는 것입니다.

ex) A =1 , C= 2, G = 3 , T= 4 이고 S가 S = CAGCCTA 일 때, P[0] = 2  Q[0] = 4 이면    CAGCCTA 이 3개 값중 가장 낮은 값이 2를 반환 합니다. P와 Q의 사이즈 만큼 찾아서 그 결과인 [2,4,1]을 반환하면 됩니다.

 

// you can also use imports, for example:
// import kotlin.math.*

// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")

fun solution(S: String, P: IntArray, Q: IntArray): IntArray {
    // write your code in Kotlin
    val sAry = S.toCharArray()
    val m = P.size
    var ans = IntArray(m)
    for(i in 0 until m){
        var p = P[i]
        var q = Q[i]
        
        if(p == q){
          ans[i] = changeInt(sAry[p].toString())
        }else  if(p > q){
          ans[i] = findmin(q,p,sAry)
        }else if(p < q){
          ans[i] = findmin(p,q,sAry)
        }
        
    }
    return ans
}
fun findmin(p:Int, q:Int, s:CharArray): Int{
    var min = Int.MAX_VALUE;
    for(i in p .. q){
        var k = changeInt(s[i].toString())
        if(min > k){
            min = k;
        }
    }
    return min
}

fun changeInt(s: String):Int{
    var result = 0
    when(s){
        "A" -> result = 1
        "C" -> result = 2
        "G" -> result = 3
        "T" -> result = 4
    }
    return result
}

 정확도는 높으나 포퍼먼스가 좋지 못한 code 입니다. 딱히 긴 생각안하고 그냥 읽어 들여서 그런것 같습니다.

이 code의 점수는 62%였습니다.

 

그래서 다시 연구했습니다.

 

두 번째 방법은  String을 짤라내서 어떤 값이 포함되어 있으면 그 값을 반환하는 방법입니다.

fun solution(S: String, P: IntArray, Q: IntArray): IntArray {
    // write your code in Kotlin
    val sAry = S.toCharArray()
    val m = P.size
    var ans = IntArray(m)
    for(i in 0 until m){
        var p = P[i]
        var q = Q[i]
        if(p == q){
          ans[i] = changeInt(sAry[p].toString())
        }else  if(p > q){
            var k = S.substring(q,p+1)
            ans[i] = checkmin(k)
        }else if(p < q){
            var k = S.substring(p,q+1)
            ans[i] = checkmin(k)
        }
        
    }
    return ans
}
fun checkmin(s: String): Int{
 var result = 0
  if(s.contains("A")){
     result = 1
  }else if(s.contains("C")){
     result = 2
  }else if(s.contains("G")){
     result = 3
  }else{
     result = 4
  }
  return result
}

fun changeInt(s: String):Int{
    var result = 0
    when(s){
        "A" -> result = 1
        "C" -> result = 2
        "G" -> result = 3
        "T" -> result = 4
    }
    return result
}

 

 하지만 여전히 62%... 복잡도가 O(N*M) 으로 나옵니다. 아마 contains 채크하는 부분이 iterater 방식인 것 같습니다. 아마 O(N+M) 복잡도가 나와야 100%가 될것으로 확인되어 방법을 생각해 보았으나 찾지 못하여 구글링을 해 보았습니다.

 

그래서 구글링을 통하여 해결 방법을 찾아보았습니다.

 

 알고리즘 문제를 풀 때 시간복잡도를 줄이기 위해서는 여러개의 Count를 쓰는 방법들이 이용된다고 합니다. 마찬가지로 이문제에서도 Count를 이용하는데 각 A, C, G, T 항목에 대한 카운터를 사용합니다. 인덱스 0부터 카운트 하기 때문에 String S의 length + 1 크기입니다. (T의 경우엔 최대값 + 남은 경우이므로 카운트 할 필요가 없다.)

새로운 문자가 들어올 때마다 각 문자에 대한 값을 올린 배열을 만든 후, 각 M개의 Query의 범위 P[K] ~ Q[K]의 최소값을 탐색합니다.

ex] CAGCCTA

A = [00111112], C = [01112333], G = [00011111] 의 Counter 가 있을 때 각 범위에서

A가 존재한다는 의미는 A[P[K]] != A[Q[K]+1] 일경우 정확히는 뒤의 값이 더 클 때입니다. 그리고 최소인값은 A->C->G->T 순서로 각 카운터를 검사해보고 제일 처음 나오는 경우 그 대응 값을 return  배열에 넣으면 됩니다.

fun solution(S: String, P: IntArray, Q: IntArray): IntArray {
        val A = IntArray(S.length + 1)
    val C = IntArray(S.length + 1)
    val G = IntArray(S.length + 1)

    val chars = S.toCharArray()
    for (i in chars.indices) {
        when (chars[i]) {
            'A' -> A[i + 1]++
            'C' -> C[i + 1]++
            'G' -> G[i + 1]++
            else -> {
            }
        }

        A[i + 1] += A[i]
        C[i + 1] += C[i]
        G[i + 1] += G[i]
    }

    val answer = IntArray(P.size)

    for (i in answer.indices) {
        val startIndex = P[i]
        val endIndex = Q[i]

        if (startIndex == endIndex) {
            val c = S[startIndex]

            when (c) {
                'A' -> answer[i] = 1
                'C' -> answer[i] = 2
                'G' -> answer[i] = 3
                'T' -> answer[i] = 4
            }
        } else if (A[startIndex] != A[endIndex + 1]) {
            answer[i] = 1
        } else if (C[startIndex] != C[endIndex + 1]) {
            answer[i] = 2
        } else if (G[startIndex] != G[endIndex + 1]) {
            answer[i] = 3
        } else {
            answer[i] = 4
        }
    }

    return answer
}

위 방법을 사용하면 다음과 같은 결과를 볼 수 있습니다.

 

 

참고

https://siyoon210.tistory.com/123

코딜리티(Codility) - GenomicRangeQuery

https://denken-y.tistory.com/entry/Codility-GenomicRangeQuery

[Codility] GenomicRangeQuery