안녕하세요! 오늘은 LeetCode의 Medium 문제인 187. Repeated DNA Sequences를 풀면서 겪었던 시간 초과(Time Limit Exceeded, TLE) 문제와 이를 해결하기 위한 여정을 공유하고자 합니다.
간단해 보이는 문제였지만, Swift의 문자열 처리 성능 특성 때문에 예상치 못한 난관에 부딪혔고 하지만 결국 의외의 결과로 풀렸습니다.
🧬 문제 소개: 반복되는 10글자 DNA 시퀀스 찾기
문제는 간단합니다. 'A', 'C', 'G', 'T'로 구성된 DNA 시퀀스 문자열 s가 주어지면, 그 안에서 두 번 이상 나타나는 10글자 길이의 모든 부분 문자열을 찾아 반환하는 것입니다.
예시:
s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"->["AAAAACCCCC", "CCCCCAAAAA"]s = "AAAAAAAAAAAAA"->["AAAAAAAAAA"]
제약 조건:
1 <= s.length <= 10^5s[i]는 'A', 'C', 'G', 'T' 중 하나
문자열 길이가 최대 10만까지 가능하므로, 효율적인 알고리즘이 필요합니다.
⏳ 시도 1: 가장 직관적인 접근 (그리고 TLE 💥)
가장 먼저 떠오른 방법은 슬라이딩 윈도우와 딕셔너리를 사용하는 것입니다.
- 10글자 크기의 윈도우를 문자열 처음부터 끝까지 한 칸씩 이동시킨다.
- 각 윈도우에 해당하는 10글자 부분 문자열을 추출한다.
- 딕셔너리를 사용하여 각 부분 문자열의 등장 횟수를 센다.
- 등장 횟수가 2 이상인 부분 문자열들을 반환한다.
// 시도 1: 슬라이딩 윈도우 + 딕셔너리
func findRepeatedDnaSequences_v1(_ s: String) -> [String] {
guard s.count > 10 else { return [] }
// 문자열을 String 배열로 변환
var value = s.map { String($0) }
var container = [String: Int]() // 빈도수 저장
var firstIndex = 0
var lastIndex = 9
while lastIndex < s.count {
// 배열 슬라이싱 후 문자열로 결합
let subString = value[firstIndex...lastIndex].joined()
container[subString, default: 0] += 1
firstIndex += 1
lastIndex += 1
}
return container.filter { $0.value > 1 }.map { $0.key }
}결과: Time Limit Exceeded (TLE). 루프 안에서 매번 배열 슬라이싱 후 joined()로 새 문자열을 생성하는 비용이 N(문자열 길이)에 비례하고,
이를 N번 가까이 반복하니 O(N*L) (L=10)의 복잡도로는 105 길이를 감당하기 어려웠습니다.
🤔 시도 2: String.Index와 Set으로 개선 (하지만 또 TLE 💥)
첫 번째 시도의 문제점인 비효율적인 문자열 생성을 개선하기 위해 String.Index를 직접 사용하고, 빈도수 계산 대신 Set을 활용하여 존재 여부를 확인하는 방식으로 변경했습니다.
seenSet: 한 번이라도 본 시퀀스를 저장합니다.repeatedSet: 두 번 이상 본 시퀀스(결과)를 저장합니다.Set.insert()의 반환값inserted: Bool을 활용하여 이미seenSet에 있는지 확인합니다.
// 시도 2: String.Index + Set
func findRepeatedDnaSequences_v2(_ s: String) -> [String] {
guard s.count > 10 else { return [] }
var seen = Set<String>()
var repeated = Set<String>()
let n = s.count
let sequenceLength = 10
for i in 0...(n - sequenceLength) {
// String.Index 계산
let firstIndex = s.index(s.startIndex, offsetBy: i)
let lastIndex = s.index(firstIndex, offsetBy: sequenceLength)
// String.Index 기반 부분 문자열 생성
let subString = String(s[firstIndex..<lastIndex])
// insert() 반환값으로 중복 확인
if !seen.insert(subString).inserted {
repeated.insert(subString)
}
}
return Array(repeated)
}결과: 또 Time Limit Exceeded (TLE). 이 결과는 조금 의외였습니다. String.Index를 사용하면 더 효율적일 것이라 기대했지만,
루프 내에서 반복적으로 s.index(...)를 호출하고 String(...)으로 부분 문자열을 생성하는 비용이 여전히 컸던 것입니다.
Swift의 String 인덱싱은 유니코드 처리 등으로 인해 단순 정수 오프셋보다 복잡할 수 있습니다.
✨ 시도 3: Character 배열 슬라이싱 (이게 왜 통과지? 🤔)
두 번째 시도마저 실패하자, 혹시나 하는 마음에 문자열을 미리 Character 배열로 변환한 뒤, 루프 내에서는 정수 인덱스를 이용한 배열 슬라이싱으로 부분 문자열을 만드는 방식을 시도했습니다.
// 시도 3: Character 배열 슬라이싱 + Set
func findRepeatedDnaSequences_v3(_ s: String) -> [String] {
guard s.count >= 10 else { return [] } // (제약조건 >= 10 으로 수정)
var seen = Set<String>()
var repeated = Set<String>()
// ✨ 문자열을 Character 배열로 미리 변환
let chars = Array(s)
for i in 0...(s.count - 10) {
// ✨ 정수 인덱스로 배열 슬라이싱 후 문자열 생성
let sub = String(chars[i..<i+10])
// 여기서는 contains + insert 사용 (기능은 동일)
if seen.contains(sub) {
repeated.insert(sub)
} else {
seen.insert(sub)
}
}
return Array(repeated)
}결과: Accepted! 🎉 놀랍게도 이 코드는 시간 제한을 통과했습니다.
왜 통과했을까? 시도 2와 시도 3 모두 루프 내에서 10글자 부분 문자열을 생성하고 Set에 넣는 로직은 동일합니다. 차이점은 부분 문자열을 만드는 방식입니다.
- 시도 2:
String.Index계산 +String에서 직접 부분 문자열 생성 - 시도 3:
Character배열로 사전 변환 + 정수 기반 배열 슬라이싱 후 부분 문자열 생성
결론적으로, Swift에서는 문자열을 미리 Character 배열로 변환한 뒤 정수 인덱스로 배열 슬라이싱을 하는 것이, 루프 내에서 반복적으로 String.Index를 계산하며 부분 문자열을 만드는 것보다 이 문제에서는 더 빨랐던 것입니다. 초기 배열 변환 비용이 있지만, 루프 내 연산이 훨씬 가벼워져 전체 실행 시간이 단축된 것으로 보입니다. (Swift 문자열 성능의 미묘함!)
✨ 배운 점 및 교훈
- Swift 문자열 성능의 미묘함:
String.Index기반 연산보다Character배열 변환 후 정수 인덱스 슬라이싱이 더 빠를 수 있습니다. 성능이 중요한 경우, 실제 테스트를 통해 확인하는 것이 좋습니다. - TLE 디버깅: 시간 초과가 발생하면 알고리즘의 시간 복잡도뿐만 아니라, 반복문 내의 구체적인 연산 비용(특히 문자열 생성, 해싱 등)을 면밀히 분석해야 합니다.
Set.insert()반환값 활용: 요소 존재 여부 확인과 삽입을 동시에 처리하는 유용한 방법입니다.
긴 삽질기였지만, 덕분에 Swift 문자열 처리의 특성과 다양한 최적화 기법에 대해 깊이 이해할 수 있었습니다. 여러분도 비슷한 문제에 부딪혔을 때 이 글이 도움이 되기를 바랍니다!
