Swift) GenomicRangeQuery in Codility

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

GenomicRangeQuery coding task - Learn to Code - Codility

출처: Codility
분류: Lesson5 Prefix Sums 

---

개인적으로 매우 매우 고통 받았던 문제입니다.. "푸는 것" 자체는 어렵지 않게 할 수 있으나 시간 복잡도를 통과하기가 굉장히 어려웠습니다.. Hㅏ....

문제를 간단히 요약하면

ACGT 로 이루어진 유전자 배열 S와 유전자의 부분의 인덱스가 들어있는 P, Q가 주어지고

P[i] ... Q[i] 범위의 S의 최소값들을 구하는 문제입니다.

 

다음과 같은 풀이 과정을 거쳤습니다. (도저히 시간 복잡도를 통과하지 못해 마지막엔 결국 다른 분들의 풀이를 참고하였습니다.)

이러한 풀이 과정은 알아두면 다른 곳에도 매우 유용할 것 같으니 아직 못푸셨다면 스스로 충분히 생각해보시고 보시는 것을 추천드립니다.고통이 클수록 열매는 단 법이겠죠!!

 

 삽질의 과정들...

1. 75%, O(N*M) (정확도 100%, 시간복잡도 33%)

문자열 -> Int 배열로 변환


min = 4라는 변수를 하나 두고

배열의 P[i]...Q[i] 인덱스를 돌면서 min보다 더 작은 값이 있다면 최소로 변경해줌.

2.최악

문자열 -> Int로 변환하는 불필요한 과정이 문제인가 싶어 그 과정을 없앴으나 

Swift에서 string 인덱스로 접근하니 속도가 더 안나옴

 

3. 75%, O(N*M) (정확도 100%, 시간복잡도 33%)

시간 복잡도 통과를 못하는 케이스는 2가지였다.
한 가지 문자열로 이루어진 매우 긴 스트링,
매우 긴 스트링

한 가지 문자열이 계속 나오는 경우도 있겠다 싶어 flag를 두고 1, 2, 3, 4중 최소, 최대가 무엇인지 확인하려 했으나..
역시 속도에는 별 영향을 (전혀ㅕㅕㅕ) 미치지 못했다.

 

4. 75%, O(N*M) (정확도 100%, 시간복잡도 33%)

다른 분들의 풀이를 참고해 a, c, g, t의 각 배열을 얻는 것 까지는 성공했으나

확인 과정에서 아래와 같이 또 다시 순회하는 같은 방법을 사용함으로써 또 다시 실패.

for i in from+1...to+1 {
  if arr[i] > flag {
  	return true
  }
}

 

 

(쓰다보니 다음부터 말투가 바꼈으나 그냥 그대로...)

삽질의 과정들을 거치고 결국 다른 분의 풀이를 참고다. 매우 신박했다.. 

우리는 특정 범위에서 최소값만 구하면 된다. 따라서 해당 부분에서 a, c, g, t 중 특정 문자열이 한 번 이라도 등장했는지 여부가 중요하다.

따라서 a, c, g, t라는 배열을 각각 만들어서 특정 인덱스에서 해당 문자가 다시 나왔을 경우에만 파악해주면 된다.

파악하는 방법으로 자신이 나오면 +1을 해주고 자신이 아니라면 이전 값과 동일한 값을 갖는다.

이때 이전과 비교하기 위해 맨 처음 인덱스는 0으로 두고 1번 인덱스부터 시작한다. (첫번째에 자신이 등장했다면 이전과 비교할 방법이 없으니까)

말로는 조금 이해가 어려우니 바로 예를 살펴보자.

문제의 예처럼 S = "CAGCCTA" 라면,

s =     "C A G C C T A"
a = [0, 0, 1, 1, 1, 1, 1, 2]
c = [0, 1, 1, 1, 2, 3, 3, 3]
g = [0, 0, 0, 1, 1, 1, 1, 1]
t = [0, 0, 0, 0, 0, 0, 1, 0]

이때 앞의 3개에 모두 해당하지 않으면 남은 하나가 될테니 마지막 t 배열은 생략해도 된다.

 

여기까지 왔다면 거의 성공이다. 마지막으로 중요한 것은 이제 이러한 도구(배열)를 가지고 비교하는 방법이다.

이 배열을 가지고 다시 주어진 범위를 돌면서 이전과 달라졌는지 확인한다면 앞의 방법과 시간적으로 별로 차이가 없다. (저처럼...)

애써 숫자로 표현한 이유는 우리가 비교하려는 대상과 마지막 대상의 차가 0보다 크기만 하면 된다.

포인트는 비교 대상과 마지막 대상 딱 둘 만 놓고 비교를 할 수 있게 되었다는 것이다.

이제 최소인 a부터 시작해 최소가 들어있는지 확인하면 된다.

P[i]를 from, Q[i]를 to 라고 한다면, 

a[from] - a[to+1] 이 0인지만 확인하면 된다.

 

두서없이 쓴 글이라 도움이 되셨을라나 모르겠네요.. 미래의 저는 알아볼 수 있겠죠 :)

감사합니다!

func haveMin(array arr: [Int], from: Int, to: Int) -> Bool {
    let min = arr[from]
    let max = arr[to+1]
    
    if max - min > 0 {
        return true
    } else {
        return false
    }
 
    
    return false
}

public func solution(_ S : inout String, _ P : inout [Int], _ Q : inout [Int]) -> [Int] {
    
    var result = [Int]()

    var a = [0]
    var c = [0]
    var g = [0]
    
    for (i, s) in S.enumerated() {
        switch s {
        case "A":
            a.append(a[i]+1)
            c.append(c[i])
            g.append(g[i])
        case "C":
            a.append(a[i])
            c.append(c[i]+1)
            g.append(g[i])
        case "G":
            a.append(a[i])
            c.append(c[i])
            g.append(g[i]+1)
        default:
            a.append(a[i])
            c.append(c[i])
            g.append(g[i])
        }
    }
    
    for i in 0..<P.count {
        if haveMin(array: a, from: P[i], to: Q[i]) {
            result.append(1)
        } else if haveMin(array: c, from: P[i], to: Q[i]) {
            result.append(2)
        } else if haveMin(array: g, from: P[i], to: Q[i]) {
            result.append(3)
        } else {
            result.append(4)
        }
    }
    
    return result
}