[Codility]GenomicRangeQuery (Python, Kotlin)

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

Codility

문제 설명

A:1, C:2, G:3, T:4 이며 'A,C,G,T'로 이루어진 문자열 S를 P[i]부터 Q[i]까지 범위의 인덱스로 잘랐을 때

해당 문자열 내의 최솟값을 구하는 문제이다.

 

즉, 'CAGCCTA' 라는 문자열 S가 주어지고, P[0] = 2, Q[0] = 4 이면

자른 문자열은 GCC가 되고 여기서 최솟값은 C = 2가 된다.

---

풀이 과정

이 문제를 풀면서 굉장히 의아한 부분이 있다.

먼저, 문제의 의도는 Prefix Sum을 이용하는 문제이지만, 파이썬으로 풀었을 때 굉장히 간단한 방법으로 다음과 같이 풀어보았다.

 

[파이썬 코드]

def solution(S, P, Q):
    arr = []
    for i in range(len(P)):
        A = P[i]
        B = Q[i]
        tmp = S[A:B+1]

        if 'A' in tmp:
            arr.append(1)
        elif 'C' in tmp:
            arr.append(2)
        elif 'G' in tmp:
            arr.append(3)
        else:
            arr.append(4)
        
    return arr

이 코드로 시간복잡도가 O(N+M)이 나오며 효율성까지 100% 통과하며 만점을 받았다.

 

이 코드를 코틀린으로 변환하면 다음과 같다.

[코틀린 코드]

fun solution(S: String, P: IntArray, Q: IntArray): IntArray {
    val arr = IntArray(P.size){0}
    for(i in P.indices) {
        val tmp = S.substring(P[i], Q[i]+1)
        if(tmp.contains('A')) {
            arr[i] = 1
        } else if(tmp.contains('C')) {
            arr[i] = 2
        } else if(tmp.contains('G')) {
            arr[i] = 3
        } else {
            arr[i] = 4
        }
    }

    return arr
}

하지만 코틀린 코드는 시간복잡도 O(N*M)이 나오며 효율성에서 통과하지 못했다.

 

두 코드를 단순 비교했을 때는 분명히 같은 코드이며

둘다 O(N*M)으로 작동하는 것이 맞지만

왜 파이썬은 O(N+M)이 나오고, 파이썬만 통과하는지 이해가 되지 않는다.

 

전체 문자열의 길이만큼 for문을 돌기 때문에 N이 발생하고

그 안에서 파이썬은 in(O(N)), 코틀린은 contains(O(N)) 이 발생하기 때문에

결국엔 O(N*M)이 발생하는 것이 맞는 것 같은데...왜 파이썬만 O(N+M)으로써 통과되는지 모르겠다...

 

(혹시 아시는분이 계시다면 댓글 부탁드리겠습니다.)

 

단순히 언어의 작동방식 차이인지...아직까지 해결을 하지 못했다 ...

일단은 prefix sum을 이용하지 않는 방식으로 해결을 하였고

prefix sum으로 다시 풀어본 뒤 재 업로드를 하려고 한다.