풀이1:
public func solution(_ S : inout String, _ P : inout [Int], _ Q : inout [Int]) -> [Int] {
let impactFactor: [String: Int] = ["A": 1, "C": 2, "G": 3, "T": 4]
var result: [Int] = []
for i in 0..<P.count {
let lowerBound = P[i]
let upperBound = Q[i]
var minimumImpactFactor = 4
for j in lowerBound...upperBound {
let targetIndex = S.index(S.startIndex, offsetBy: j)
let nucleotide = String(S[targetIndex])
guard let impactFactor = impactFactor[nucleotide] else {
break
}
minimumImpactFactor = min(minimumImpactFactor, impactFactor)
}
result.append(minimumImpactFactor)
}
return result
}시간복잡도 O(N*M) 으로 효율성 테스트에서 실패
풀이2:
public func solution(_ S : inout String, _ P : inout [Int], _ Q : inout [Int]) -> [Int] {
var nucleotideCounter: [Int] = [Int](repeating: 0, count: 4)
var counters: [[Int]] = [nucleotideCounter]
for char in S {
switch char {
case "A": nucleotideCounter[0] += 1
case "C": nucleotideCounter[1] += 1
case "G": nucleotideCounter[2] += 1
case "T": nucleotideCounter[3] += 1
default: continue
}
counters.append(nucleotideCounter)
}
var result = [Int]()
for i in 0..<P.count {
let (lowerBound, upperBound) = (P[i], Q[i]+1)
let (upperBoundArray, lowerBoundArray) = (counters[upperBound], counters[lowerBound])
for j in 0..<nucleotideCounter.count {
let hasNucleotide = upperBoundArray[j] - lowerBoundArray[j] > 0
if hasNucleotide {
let impactFactor = j+1
result.append(impactFactor)
break
}
}
}
return result
}염기서열을 순회하면서 각 염기마다 카운트를 해준다.
매번 카운트할 때마다 새로운 배열을 생성해서 이차원 배열에 넣는다.
그리고 염기서열의 각 범위에 카운트를 조회하고 그 둘의 차이를 구한다.
만약 값이 0보다 크면 해당 염기가 존재하는 것이므로 결과에 넣는다.
impactFactor이 작은 것에서 큰 순서대로 염기 기록을 순회하므로 가장 작은 것을 찾을 필요는 없다. ([A, C, G, T] 순서)
예시처럼 염기서열이 CAGCCTA 인 경우 2차원 배열의 모습:
인덱스 : 염기서열
[0 : [0,0,0,0]
1 : [0,1,0,0] C 카운트
2 : [1,1,0,0] A 카운트
3 : [1,1,1,0] G 카운트
4 : [1,2,1,0] C 카운트
5 : [1,3,1,0] C 카운트
6 : [1,3,1,1] T 카운트
7 : [2,3,1,1] ] A 카운트
염기서열과 인덱스
C A G C C T A
0 1 2 3 4 5 6
위 2차원 배열을 이용해서 위 염기 서열의 2번째 4번째 염기간 가장 작은 impact factor을 구해야한다면 어떻게 해야할까?
2번째에 위치한 G가 카운트된 시점의 염기들의 카운트부터 4번째에 위치한 C가 카운트된 시점의 염기들의 카운트를 이용하면 어떨까?
먼저 4번째에 위치한 C가 카운트된 시점의 염기 카운트는 [1,3,1,0]으로 이차원배열의 5번째 인덱스에 위치해있다.
그리고 2번째에 위치한 G가 카운트된 시점의 염기 카운트는 [1,1,1,0]으로 이차원 배열의 3번째 인덱스에 위치해있다.
두 염기 카운트의 차를 구해보면 그 사이에 존재하는 염기들의 카운트를 구할 수 있어보인다.
두 염기 카운트의 차를 구해보니 [0,2,0,0]이다. C가 두개 있었다는 이야기가 된다.
그런데 여기서 짚고 가야할 중요한 부분이 하나 있다. 2번째와 4번째 간 염기는 G C C이다. 그러나 좀 전에 계산에 의하면 C가 두개로 나타났다. 이 차이는 왜 발생하는 걸까?
이 차이는 2번째 위치한 G가 카운트된 시점의 염기를 빼므로써, G를 빼는 것이 되버린다. 따라서 해당 염기 카운트의 직전의 값을 이용해야한다. 이차원 배열의 3번째가 아닌 2번째 인덱스의 값을 사용해야한다.
자 이제 다시 [1,3,1,0]과 [1,1,0,0] 차이를 구하면, [0,2,1,0]으로, G 하나 C 둘이 나온다. 보다 더 정확한 계산이 되었다.
이러한 방법으로 각 염기 카운트간에 존재하는 염기 값을 구하면 시간 복잡도를 O(N+M)으로 문제를 통과할 수 있게 된다.
풀이 3:
public func solution(_ S : inout String, _ P : inout [Int], _ Q : inout [Int]) -> [Int] {
var A = [Int](repeating: 0, count: S.count+1),
C = [Int](repeating: 0, count: S.count+1),
G = [Int](repeating: 0, count: S.count+1),
T = [Int](repeating: 0, count: S.count+1)
for (i, char) in S.enumerated() {
A[i+1] = A[i]
C[i+1] = C[i]
G[i+1] = G[i]
T[i+1] = T[i]
switch char {
case "A":
A[i+1] += 1
case "C":
C[i+1] += 1
case "G":
G[i+1] += 1
case "T":
T[i+1] += 1
default:
continue
}
}
var result = [Int]()
for i in 0..<P.count {
let (lowerBound, upperBound) = (P[i], Q[i]+1)
if A[upperBound] - A[lowerBound] > 0 {
result.append(1)
} else if C[upperBound] - C[lowerBound] > 0 {
result.append(2)
} else if G[upperBound] - G[lowerBound] > 0 {
result.append(3)
} else {
result.append(4)
}
}
return result
}검색으로 알게된 신선한 풀이법이나 개인적으로 풀이2가 더 직관적으로 와닿는다.
upperBound에 1을 더해준 이유는, 위의 ACGT배열에 카운트를 하는 과정에서 해당 염기가 발견된 경우 다음 인덱스인 i+1에 해주기 때문이다. upperBound에 1을 더한 범위로 조회해야 정확하게 찾을 수 있다.
만약 풀이 이해에 어려움이 있다면 한번 수기로 적어보면 단번에 이해가 될 것이다.
