[Swift 알고리즘] GenomicRangeQuery - Codility

GenomicRangeQuery coding task - Learn to Code - Codility

---

문제 분석

A, C, G, T : 1, 2, 3, 4에 대응하는 염기서열
P, Q 배열은 각각 범위에 대한 정보 -> [Pn...Qn]의 범위
해당 범위 내의 염기서열에 대응하는 factor의 값 중 가장 작은 것을 return
O(N * M) == 5 * 10 ** 9이므로, 시간 초과

의사 코드 (오답)

A C G T와 factor 값을 대응시킨 딕셔너리 생성
answer: [Int] 변수에 정답 저장
M만큼 반복하며, 매 반복마다, 주어진 S에서 Pn...Qn 범위에 해당하는 Array를 생성
    최솟값을 저장할 변수 
    Array를 탐색하며, 각 원소에 대응하는 factor를 딕셔너리로 접근하고, 최솟값을 갱신
    혹은 Array 생성 단계에서, factor 값으로 정수형 배열을 생성하고 min()
    반복 종료되면 answer에 append
return answer

나의 풀이 (오답)

import Foundation
import Glibc

public func solution(_ S : inout String, _ P : inout [Int], _ Q : inout [Int]) -> [Int] {
    let nucleotidesDict = ["A" : 1, "C": 2, "G": 3, "T": 4]
    let arrSize = P.count
    var answer = [Int]()

    for i in 0..<arrSize {
        let start = S.index(S.startIndex, offsetBy: P[i])
        let end = S.index(S.startIndex, offsetBy: Q[i])
        let minValue = S[start...end]
            .compactMap { nucleotidesDict[String($0)] }
            .min()!        
        answer.append(minValue)
    }

    return answer
}

// O(N * M)

 

시간 초과가 날 것을 알면서도 기본적인 방식으로 풀이해봤다.

.compactMap()을 사용하면 forced-unwrap을 하지 않아도 된다는 점,

메서드를 이어서 사용할 경우, 메서드마다 라인을 나누면 가독성이 낫다는 점을 배웠다.

더 나은 풀이

// 개선된 풀이
// S에서 A, C, G, T가 등장하는 횟수를 세는 누적합 배열을 각각 만들어준다.
// Pn...Qn 범위에서, 누적합 배열의 Qn - Pn의 값이 0보다 크면, 해당 문자가 있는 것
    // A > C > G > T의 우선도로 먼저 등장하는 것의 factor를 ans에 append

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
}

// O(N + M)

 

풀이가 생각나지 않아 다른 블로그를 참고했다.

각 알파벳마다 누적합 배열을 만들고, S를 탐색하며 배열을 갱신한다.

이때 배열을 첫 번째 값을 0으로 설정하고, 배열의 길이를 S+1로 하는 것이 중요하다.

(Q[i] + 1) - (P[i])의 차이가 0보다 크면, 해당 염기서열에 대응하는 값을 ans에 추가한다. (이때 우선 순위는 A > C > G > T)

(Q[i] + 1) - (P[i])인 이유: 누적합 배열 길이가 S+1 이므로, 문자열 i == 누적합 배열 i +1

 

참고

https://borabong.tistory.com/37

https://woongsios.tistory.com/68