[Codility] 5.GenomicRangeQuery

문제 링크

GenomicRangeQuery

문제 요약

String 문자열 S가 주어진다.
나타날 수 있는 문자열의 합은 A,C,G,T 중 무작위 요소로 구성되어 있다.
S가 DNA 구조라고 할 때, 부분 요소를 Array P, Q가 주어진다.

S가 가령 CAGCCTA 일 때
P[0] = 2, Q[0] = 4
S의 2~4 index는 G,C,C이다. 각 요소는 문제에서 3, 2, 2로 매칭된다.
여기서 최소값을 구한다면 2가된다.
이런식으로 N-1까지의 부분 요소를 갖는 최소 배열을 구하라.

요구사항

N is an integer within the range [1..100,000]
M is an integer within the range [1..50,000]
each element of arrays P and Q is an integer within the range [0..N - 1]
P[K] ≤ Q[K], where 0 ≤ K < M
string S consists only of upper-case English letters A, C, G, T

코드

문제 이해자체는 그리 어렵진 않지만 구현하는데 힘들었다.
처음에는 substring으로 구간별로 array를 만들어서 Set으로 값이 들어있는지 확인하며 풀려고 했지만 리턴형식을 substring의 리턴값을 String< array>로 못해 실패.

ググっちゃった！笑笑
각 요소가 S를 순회하며 턴마다 포함 상황을 담은 배열(arrA, arrC...)을 만들고,
각 배열의 요구 구간(P[i]~Q[i])에 따라 처음과 끝 값이 다르다면 요구 구간에서 나온 것을 적용

import Foundation
import Glibc

private func haveMin(array arr: [Int], from: Int, to: Int) -> Bool {
    let minVal = arr[from]
    let maxVal = arr[to+1]

    if maxVal - minVal > 0 {
        return true
    } else {
        return false
    }

}

public func solution(_ S : inout String, _ P : inout [Int], _ Q : inout [Int]) -> [Int] {
    var arrA: [Int] = [0]
    var arrC: [Int] = [0]
    var arrG: [Int] = [0]
    var resultArr = [Int]()
    
    for (idx, value) in S.enumerated() {
        switch value {
            case "A":
                arrA.append(arrA[idx]+1)
                arrC.append(arrC[idx])
                arrG.append(arrG[idx])
            
            case "C":
                arrA.append(arrA[idx])
                arrC.append(arrC[idx]+1)
                arrG.append(arrG[idx])
            
            case "G":
                arrA.append(arrA[idx])
                arrC.append(arrC[idx])
                arrG.append(arrG[idx]+1)

            default:
                arrA.append(arrA[idx])
                arrC.append(arrC[idx])
                arrG.append(arrG[idx])                       
        }
    } 

    for i in 0..<P.count {
        if haveMin(array: arrA, from: P[i], to: Q[i]) {
            resultArr.append(1)
        } else if haveMin(array: arrC, from: P[i], to: Q[i]) {
            resultArr.append(2)
        } else if haveMin(array: arrG, from: P[i], to: Q[i]) {
            resultArr.append(3)
        } else {
            resultArr.append(4)
        }
    }
    return resultArr

}