leetcode 187. Repeated DNA Sequences

문제 개요

문제의 목표는 주어진 DNA 문자열 s에서 길이가 10인 모든 부분 문자열 중 두 번 이상 등장하는 시퀀스를 찾는 것입니다.
DNA 문자열은 오직 'A', 'C', 'G', 'T'로 이루어져 있습니다.

접근 방식

이 문제를 해결하기 위해 다음과 같은 아이디어를 사용하였습니다:

1. 문자열 슬라이싱을 통한 부분 문자열 추출:
   • 문자열을 문자 배열로 변환한 뒤, 시작 인덱스부터 10글자씩 추출합니다.
2. 해시 테이블 사용:
   • 각 추출한 10글자 시퀀스의 등장 횟수를 저장하기 위해 Dictionary<String, Int>를 사용합니다.
   • 등장 횟수가 2가 되는 순간 해당 시퀀스를 결과 배열에 추가합니다.
3. 시간 복잡도:
   • O(n) 시간에 문제를 해결할 수 있습니다. n은 문자열의 길이이며, 각 부분문자열을 O(1) 또는 O(10) 시간으로 추출합니다.
4. 공간 복잡도:
   • 최악의 경우 모든 10글자 시퀀스가 다를 경우 O(n) 공간을 사용하게 됩니다.

학습한 키워드 및 개념

• 슬라이싱 (Slicing): 배열 또는 문자열에서 특정 구간의 원소를 추출하는 방법.
• 해시 테이블 (Hash Table): 키-값 쌍을 저장하여 빠른 조회를 가능하게 하는 자료구조.
• 시간 복잡도 (Time Complexity): 알고리즘의 실행 시간을 설명하는 척도.
• 공간 복잡도 (Space Complexity): 알고리즘에 필요한 메모리 사용량에 대한 척도.

제출코드

// LeetCode의 Repeated DNA Sequences 문제를 해결하는 클래스입니다.
class Solution {
    // findRepeatedDnaSequences 함수: 주어진 DNA 문자열 s 내에서 10글자 부분 문자열 중 
    // 두 번 이상 등장하는 시퀀스를 찾아 반환합니다.
    func findRepeatedDnaSequences(_ s: String) -> [String] {
        // DNA 문자열의 길이가 10보다 작으면 중복된 시퀀스가 있을 수 없으므로 빈 배열 반환
        guard s.count > 10 else { return [] }
        
        // 각 시퀀스가 몇 번 등장했는지 저장하기 위한 딕셔너리
        var seen = [String: Int]()
        // 두 번 이상 등장한 시퀀스를 저장할 배열
        var result = [String]()
        // 문자열을 문자 배열로 변환하여 슬라이싱 작업을 쉽게 합니다.
        let arr = Array(s)
        
        // 배열의 각 인덱스부터 10글자씩 잘라서 부분 문자열을 추출합니다.
        for i in 0...arr.count - 10 {
            // i부터 i+10 인덱스 범위의 문자들을 문자열로 변환
            let sub = String(arr[i..<i+10])
            // 해당 부분 문자열의 등장 횟수를 증가시킵니다 (기본값은 0)
            seen[sub, default: 0] += 1
            
            // 만약 이 부분 문자열이 두 번째로 등장하는 경우 결과 배열에 추가합니다.
            if seen[sub] == 2 {
                result.append(sub)
            }
        }
        
        // 중복된 시퀀스들의 배열을 반환합니다.
        return result
    }
}

알고리즘 분석 및 학습 포인트

• 슬라이싱의 효율성:
  DNA 문자열을 배열로 변환한 후 슬라이싱하는 방식은 구현이 간단하며 Swift에서 자주 사용하는 기법입니다.
  단, 문자열의 길이가 매우 긴 경우 메모리 사용량에 유의해야 합니다.
• 딕셔너리 사용:
  Swift의 Dictionary는 해시 테이블 기반으로, 평균적으로 O(1)의 시간 복잡도를 갖습니다.
  이 문제에서는 각 시퀀스에 대해 등장 횟수를 빠르게 조회할 수 있어 매우 효율적입니다.
• 조건부 추가:
  등장 횟수가 2가 되는 시점에 결과에 추가하는 조건은 중복 추가를 막아주는 좋은 전략입니다.
• Swift 가이드라인 준수:
  코드 내 네이밍과 구조는 Swift API Guidelines에 따라 간결하고 명확하게 작성되었습니다.
  만약 Swift Guideline에 어긋난 부분이 있다면 피드백 해주시면 감사하겠습니다.