안녕하세요 코코종입니다.
간~~만에 코딜리티 문제를 풀러 왔어효.. (진짜 너무 오랜만이네 나레기...)
몇 문제에서 느끼긴 했지만 역시 코딜리티 문제가 프로그래밍적 사고를 하는데 도움을 많이 주는거 같아요(맞왜틀?? 이러면서)
물론 연속적으로 풀지 않으면 또 까먹어버리는 나레기...
처음에 문제 이해가 가지 않아서 간단하게 문제 요약을 하겠습니다.
ACGT라는 유전자 뭐시기(나름 생2 했었는데 기억이 안나요 이름...)가 있는데 각각 1,2,3,4를 갖는다고 하네요
이때 P와 Q가 주어지는데 (여기가 첨에 뭔말인가 했네요...) DNA를 자를때 그 범위를 알려준다고 보면 됩니다.
P[k]...Q[k] 까지로 자른다! 이렇게요
그 잘라진 DNA에서의 가장 작은 값을 (A가 1 이런식으로요!) 순서대로 배열에 담아서 리턴하면 되는 문제였습니다.
'아 쉽네' 하면서 바로 풀었습니다! 말한 그~~대로 구현해버렸기 때문에 당연히 틀렸더라구요 (맨날 코딜리티 풀때마다 이래,,,)
시간 복잡도 면에서 M*N이 나와가지구 틀렸습니당 ㅎ...for문 안에서 또 min()으로 모든 부분 배열을 다 돌았더니 당연한 결과네요 ㅜㅜ
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] {
// Implement your solution here
var result: [Int] = []
let s = convertToIntArray(S)
for k in 0..<P.count {
let p = P[k]
let q = Q[k]
let sliced = s[p...q]
result.append(sliced.min()!)
}
return result
}
func convertToIntArray(_ str: String) -> [Int] {
var result: [Int] = []
str.forEach {
if $0 == "A" {
result.append(1)
}
if $0 == "C" {
result.append(2)
}
if $0 == "G" {
result.append(3)
}
if $0 == "T" {
result.append(4)
}
}
return result
}
// A C G T
// 1 2 3 4
// What is the minimal impact factor of nucleotides contained in a particular part of the given DNA sequence?
// 일 부분에서 가장 작은 impact factor?
// CAGCCTA
// 2132241
// ex)
// P[0] = 2 Q[0] = 4
// P[1] = 5 Q[1] = 5
// P[2] = 0 Q[2] = 6
// M = 3 -> 일때
// P[K] Q[K] 에서 가능한 K는 0...K..<M (0 <= K < M)
// p[0] = 2 q[0] = 4 -> index 2...4 (GCC == 322) 최소 2
// p[1] = 5 q[1] = 5 -> index 5...5 (T == 4) 최소 4
// ...
// return -> [0, 4, 1]그래서 저는 min()을 쓰지 않으려고 딕셔너리도 만들었다가 set으로도 했다가 다 했는데요. 결국 본질적인 문제는 'sliced를 모두 돌면 안된다' 였습니다. 하긴 처음과 끝을 자른다고 하면 첨부터 또 다시 도는거니까 비효율적이긴 하네요. (꼭..! 여러분들은 주제를 다시 생각해보고 푸세여... -> 이말 1000번째 하는데 정작 본인이 못지킴)
결론적으로 다른 분들의 풀이를 참고했는데요
A,C,G,T를 dp처럼 몇번이나 나왔는지 저장하고 그 index에 해당 하는 dp 저장값의 차를 계산해서 0보다 큰지 판단해줬습니다!
그리고 첫 dp값은 0으로 초기화를 해둬서 array[q+1] - array[p]인 점을 기억해두시길 바랍니다!
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] {
// Implement your solution here
var s: [Int] = []
var result: [Int] = []
var arrayA = [0]
var arrayC = [0]
var arrayG = [0]
var arrayT = [0]
S.forEach {
if $0 == "A" {
s.append(1)
arrayA.append(arrayA.last! + 1)
} else {
arrayA.append(arrayA.last!)
}
if $0 == "C" {
s.append(2)
arrayC.append(arrayC.last! + 1)
} else {
arrayC.append(arrayC.last!)
}
if $0 == "G" {
s.append(3)
arrayG.append(arrayG.last! + 1)
} else {
arrayG.append(arrayG.last!)
}
if $0 == "T" {
s.append(4)
arrayT.append(arrayT.last! + 1)
} else {
arrayT.append(arrayT.last!)
}
}
print(arrayA, arrayC, arrayG, arrayT)
for k in 0..<P.count {
let p = P[k]
let q = Q[k]
if arrayA[q+1] - arrayA[p] > 0 {
result.append(1)
} else if arrayC[q+1] - arrayC[p] > 0 {
result.append(2)
} else if arrayG[q+1] - arrayG[p] > 0 {
result.append(3)
} else if arrayT[q+1] - arrayT[p] > 0 {
result.append(4)
} else { // same
result.append(s[p])
}
}
return result
}
func convertToIntArray(_ str: String) -> [Int] {
var result: [Int] = []
str.forEach {
if $0 == "A" {
result.append(1)
}
if $0 == "C" {
result.append(2)
}
if $0 == "G" {
result.append(3)
}
if $0 == "T" {
result.append(4)
}
}
return result
}
// A C G T
// 1 2 3 4
// What is the minimal impact factor of nucleotides contained in a particular part of the given DNA sequence?
// 일 부분에서 가장 작은 impact factor?
// CAGCCTA
// 2132241
// ex)
// P[0] = 2 Q[0] = 4
// P[1] = 5 Q[1] = 5
// P[2] = 0 Q[2] = 6
// M = 3 -> 일때
// P[K] Q[K] 에서 가능한 K는 0...K..<M (0 <= K < M)
// p[0] = 2 q[0] = 4 -> index 2...4 (GCC == 322) 최소 2
// p[1] = 5 q[1] = 5 -> index 5...5 (T == 4) 최소 4
// ...
// return -> [0, 4, 1]뭐... 코드가 더러우면 어떻습니까 ^^ 맞춘게 중요하지(그 와중에 막 오타내고... 인덱스 잘못적고 이래서 한 20~30분간 삽질함^^)
여러분들도 꾸준히 한 문제씩 풀기로 해봐여~