Codility - GenomicRangeQuery

첫 번째 풀이

import Foundation
import Glibc

public func solution(_ S : inout String, _ P : inout [Int], _ Q : inout [Int]) -> [Int] {
    let str = Array(S)
    let factor = ["A": 1, "C": 2, "G": 3, "T": 4]
    var result = [Int]()

    for i in 0..<P.count {
        let start = P[i]
        let end = Q[i]
        var minValue = 10
        for j in start...end {
            let temp = factor[String(str[j])]!
            minValue = min(minValue, temp)
        }
        result.append(minValue)
    }

    return result
}

당연히 성능 테스트를 통과 못할 거라고 생각은 했는데 도저히 효율적인 방법이 생각이 나지 않았다.

두 번째 풀이

import Foundation
import Glibc

public func solution(_ S : inout String, _ P : inout [Int], _ Q : inout [Int]) -> [Int] {
    var result = [Int]()
    var occurrences = Array(repeating: Array(repeating: 0, count: 4), count: S.count)
    let factors = ["A": 1, "C": 2, "G": 3, "T": 4]

		// Step 1
    for (i, ch) in S.enumerated() {
        occurrences[i][factors[String(ch)]!-1] = 1
    }

		// Step 2
    for i in 1..<occurrences.count {
        for j in 0..<4 {
            occurrences[i][j] += occurrences[i-1][j]
        }
    }

		// Step 3
    for i in 0..<P.count {
        let start = P[i]
        let end = Q[i]

        for j in 0..<4 {
            let startOccurrence = start != 0 ? occurrences[start-1][j] : 0
            if occurrences[end][j] - startOccurrence > 0 {
                result.append(j+1)
                break
            }
        }
    }

    return result
}

구글링을 해서 풀이법을 참고했다. 핵심은 각 뉴클레오타이드 종류의 등장 횟수를 이용한다는 것이다.

1. S(DNA 시퀀스)를 순차적으로 돌면서 i번째에는 어떤 뉴클레오타이드가 있는지 occurrences 배열에 저장한다.
2. 이번에는 occurrences 배열을 순차적으로 돌면서 occurrences[i]에 occurrences[i-1] 배열의 값들을 더한 값을 저장한다. 그러면 occurrences[i] 에는 0~i 범위의 시퀀스에 각 뉴클레오타이드 종류의 등장 횟수가 저장된다.
3. 이제 P 배열을 순차적으로 돌면서 쿼리에 대한 답을 찾으면 된다. P[i]~Q[i] 범위 시퀀스의 occurrences는 Q[i]번째에서 P[i]-1번째 occurrences를 뺀 값이 된다. (P[i] == 0이면 아무 것도 빼주면 안 된다.)

이 코드의 시간 복잡도는 O(N+M)이다.