[Swift 알고리즘] Codility - GenomicRangeQuery

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "Codility - GenomicRangeQuery" 문제를 풀었습니다.

 

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

GenomicRangeQuery coding task - Learn to Code - Codility

 

풀이

이번 문제는 구간 안에 들어가 있는 DNA 값 중 최소값을 구하는 문제입니다.

문제 자체는 어렵지 않지만 시간 복잡도를 충족하는 것이 어려웠습니다.

 

이번 문제는 O(N+M)으로 풀어야 하는데

아무리 생각해도 O(N*M) 풀이 밖에 떠오르지 않아 다른 분의 풀이를 참고했습니다.

코딜리티를 풀면서 처음으로 못 푼 문제 같아요... ㅠㅠ

 

S에서 범위를 나눠 각 구간마다 DNA가 나오는 횟수를 count 합니다.

예제에 나온 CAGCCTA라면,

C = [0, 1, 0, 0]
CA = [1, 1, 0, 0]
CAG = [1, 1, 1, 0]
...

반복을 하는 것이죠.

 

그 뒤 P = 2, Q = 4 라면 Arr[4] - Arr[1]을 계산하면

2 ~ 4까지 들어있는 DNA의 개수를 구할 수 있습니다.

 

그러면 O(N+M)으로 해결이 됩니다! ㅠㅠ

 

분명 프로그래머스의 카카오 문제에서 다뤘던 구간합 원리였는데...

설마 이건가?까지만 생각이 가고 코드를 짜지는 못했습니다.

이런 응용 알고리즘은 아직도 많이 어렵네요.. 언제쯤 쉬워질지 모르겠어요

 

더 노력해야겠습니다.

화이팅!

 

감사합니다.

 

전체 코드

import Foundation
import Glibc

// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")

public func solution(_ S : inout String, _ P : inout [Int], _ Q : inout [Int]) -> [Int] {
    // write your code in Swift 4.2.1 (Linux)
    //ACGT -> 1234
    let dict: [Character: Int] = ["A": 0, "C": 1, "G": 2, "T": 3]
    var sequences: [[Int]] = Array(repeating: Array(repeating: 0, count: 4), count: S.count+1)

    //DNA가 들어가는 범위 count 구하기
    for (i, char) in S.enumerated() {
        sequences[i+1] = sequences[i]
        sequences[i+1][dict[char]!] += 1
    }

    var result: [Int] = []
    for i in 0..<P.count {
        let pArr = sequences[P[i]+1-1]
        var qArr = sequences[Q[i]+1]

        for i in 0..<qArr.count {
            //범위 안에 DNA가 존재하는지 확인하기
            if qArr[i] - pArr[i] > 0 { 
                result.append(i+1)
                break
            }
        }
    }
    
    return result
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.

 

Swift, Swift 알고리즘, 스위프트, 알고리즘, Codility, GenomicRangeQuery