Codility - GenomicRangeQuery

문제

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

[

GenomicRangeQuery coding task - Learn to Code - Codility

Find the minimal nucleotide from a range of sequence DNA.

app.codility.com

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

---

문제

• ACGT = [1,2,3,4]
• 염기서열이 들어있는 S가 주어진다.
• P[index] ~ Q[index] 까지의 염기서열 중 제일 작은 크기를 가져와 배열을 만든다
• 리턴

풀이

• ACGT배열을 S의 크기만큼 만든다
• A[index+1] = A[index]
• S str에서 알파벳이 나오면 A[index+1]+=1
• 범위의 처음과 끝이 바뀌았다면 해당 값 넣는다.
• ACGT순으로 검사한다.

코드

public func solution(_ S : inout String, _ P : inout [Int], _ Q : inout [Int]) -> [Int] {
    
    let sSize = S.count
    var resultArr = Array<Int>()
    var arr = Array<Array<Int>>(repeating: Array<Int>(repeating: 0, count: sSize+1), count: 4)
    var sequence: Dictionary<Character, Int> = ["A" : 1, "C": 2, "G" : 3, "T" : 4]
    var index = 0
    S.forEach { char in 
        for i in 0..<4 {
            arr[i][index+1] = arr[i][index]
        }
        switch char {
            case "A": arr[0][index+1] += 1
            case "C": arr[1][index+1] += 1
            case "G": arr[2][index+1] += 1
            case "T": arr[3][index+1] += 1
            default: break
        }
        
        index += 1
    }

    for i in 0..<P.count {
        let startIndex = P[i]
        let endIndex = Q[i]
    
        if startIndex == endIndex {
            let char = S[S.index(S.startIndex, offsetBy: startIndex)]
            resultArr.append(sequence[char]!)
            continue
        }
        for i in 0..<4 {
            if arr[i][startIndex] != arr[i][endIndex+1] {
                resultArr.append(i+1)
                break
            }
        }
    }
    
    return resultArr
}

---

생각

• 처음에 범위를 모두 지나가며 제일 작은 값을 찾는 것을 생각하였다. O(N*M)
• 이렇게 하게 되면 시간 초과가 난다. 때문에 더 빠른 방법을 모색하였다.
• 시작과 끝의 값이 다르다면 바뀐 것이기 때문에 해당 값이 들어가 있는 것을 참고하여 풀었다