[Algorithm] GenomicRangeQuery

[hwangJi-dev]

💬 문제

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

💬 Idea

• 처음엔 굉장히 간단한 문제라 생각했지만, 효율성 테스트를 통과하지 못해 굉장히 애를 썼다.
• O(N^2)의 효율성을 O(N + M)으로 높이기 위해 구간합을 사용해주었다.
• a, c, g, t 각각의 배열을 만들어 (t는 없어도 됨) 알파벳이 나온 구간에는 이전 값 + 1을 해주어 저장해준다.
• 이후 P를 돌면서 (P) 에서 (Q + 1) 까지의 차가 0 이상일 때 a,c,g,t 중 조건에 해당하는 값을 ans에 append한다.
  • Q + 1 까지인이유: 이전 인덱스와 비교하여 해당 구간에서 알파벳이 등장했는지를 파악하기 위해 배열의 인덱스를 +1 해주었기 떄문이다.

💬 풀이

public func solution(_ S : inout String, _ P : inout [Int], _ Q : inout [Int]) -> [Int] {
    var a = Array(repeating: 0, count: S.count + 1)
    var c = Array(repeating: 0, count: S.count + 1)
    var g = Array(repeating: 0, count: S.count + 1)
    var t = Array(repeating: 0, count: S.count + 1)
    var ans: [Int] = []
    
    for (idx, i) in S.enumerated() {
        a[idx + 1] = a[idx]
        c[idx + 1] = c[idx]
        g[idx + 1] = g[idx]
        t[idx + 1] = t[idx]
        
        switch i {
        case "A":
            a[idx + 1] += 1
        case "C":
            c[idx + 1] += 1
        case "G":
            g[idx + 1] += 1
        default:
            t[idx + 1] += 1
            
        }
    }
    
    for i in 0..<P.count {
        if a[Q[i] + 1] - a[P[i]] > 0 {
            ans.append(1)
        } else if c[Q[i] + 1] - c[P[i]] > 0 {
            ans.append(2)
        } else if g[Q[i] + 1] - g[P[i]] > 0 {
            ans.append(3)
        } else {
            ans.append(4)
        }
    }
    
    return ans
}

소요시간 : 1시간 +

시간 복잡도 : O(N + M)

평가표 : https://app.codility.com/demo/results/training7V4PMC-ED3/