코틀린 코딩테스트 강좌, DNA 비밀번호

코딩 테스트는 소프트웨어 개발자의 채용 과정에서 중요한 역할을 하며, 많은 기업들이 지원자의 알고리즘 문제 해결 능력을 평가하기 위해 다양한 문제를 출제합니다. 이번 장에서는 코틀린을 사용하여 ‘DNA 비밀번호’ 문제를 해결하는 방법에 대해 자세히 알아보겠습니다.

문제 설명

DNA 비밀번호 문제는 다음과 같은 조건을 가지고 있습니다:

  • DNA 비밀번호는 알파벳 A, C, G, T로 이루어진 문자열입니다.
  • 주어진 DNA 문자열에서 특정 조건을 만족하는 부분 문자열을 찾아야 합니다.
  • 각 DNA 문자열은 최소 M개의 특정 문자를 포함해야 합니다.

예를 들어, DNA 문자열이 “ACGTACGT”이고 M=2일 때, ‘A’는 2개 이상, ‘C’는 2개 이상 포함되어 있어야 합니다.

문제 예시

주어진 DNA 문자열: ACGTACGT
필요한 문자의 개수: M=2
필요한 DNA 문자: {‘A’, ‘C’}

목표

주어진 DNA 문자열에서 필요한 문자를 충족하는 모든 부분 문자열을 찾아 그 개수를 세는 것입니다.

문제 해결 접근법

이 문제를 해결하기 위해, 슬라이딩 윈도우 기법을 사용할 것입니다. 이 기법은 주어진 문자열의 윈도우를 이동시키면서 필요한 문자 수를 체크하는 방식입니다.

슬라이딩 윈도우 기법 설명

슬라이딩 윈도우는 다음과 같은 단계로 진행됩니다:

  • 윈도우의 시작점과 끝점을 설정하고, 초기 상태를 만족하는지 확인합니다.
  • 윈도우를 이동시키면서 각 위치에서 필요한 문자의 개수를 체크합니다.
  • 문자 개수가 조건을 만족하면 카운트를 증가시킵니다.

코틀린 코드 구현

다음은 DNA 비밀번호 문제의 해결을 위한 코틀린 코드입니다:


fun countDnaPasswords(dna: String, requiredChars: Set, minCount: Int): Int {
    val charCount = mutableMapOf()
    var validPasswords = 0
    var left = 0

    for (right in dna.indices) {
        charCount[dna[right]] = charCount.getOrDefault(dna[right], 0) + 1

        while (requiredChars.all { charCount.getOrDefault(it, 0) >= minCount }) {
            validPasswords++
            charCount[dna[left]] = charCount[dna[left]]!! - 1
            if (charCount[dna[left]] == 0) {
                charCount.remove(dna[left])
            }
            left++
        }
    }

    return validPasswords
}

// 사용 예시
fun main() {
    val dna = "ACGTACGT"
    val requiredChars = setOf('A', 'C')
    val minCount = 2
    println(countDnaPasswords(dna, requiredChars, minCount))  // 출력: 6
}

코드 설명

위의 코드는 다음과 같은 논리로 작동합니다:

  • 함수 정의: countDnaPasswords 함수는 DNA 문자열, 필요한 문자의 집합, 최소 포함 문자의 개수를 파라미터로 받습니다.
  • 카운트 초기화: 필요한 문자의 개수를 세기 위한 맵을 초기화합니다.
  • 슬라이딩 윈도우 구현: 오른쪽 포인터를 통해 문자열을 순회하며, 각 문자 카운트를 업데이트합니다.
  • 조건 확인: 필요한 문자가 모두 충족되면 카운트를 증가시키고, 왼쪽 포인터를 이동시켜 윈도우를 줄입니다.

복잡도 분석

위 알고리즘의 시간 복잡도는 O(n)입니다. 문자열을 한 번 순회하면서 필요한 문자를 체크하기 때문입니다. 추가적인 공간 복잡도는 O(1)로, 필요한 문자의 개수에 따라 공간이 달라질 수 있지만, 최대 4개의 문자를 저장하므로 상수 공간에 해당합니다.

결론

이번 포스팅에서는 DNA 비밀번호 문제를 통해 슬라이딩 윈도우 기법을 배우고, 코틀린을 사용하여 문제를 해결하는 방법에 대해 알아보았습니다. 이러한 알고리즘 문제는 취업 준비 과정에서 매우 유용하며, 코딩 테스트 준비에 도움이 될 것입니다. 다양한 상황에 맞게 코드를 수정하고 응용하며, 더 많은 문제를 연습해보는 것을 권장합니다.

다음 포스팅에서는 보다 다양한 알고리즘 문제를 다룰 예정이니 많은 관심 부탁드립니다!