자바 코딩테스트 강좌, DNA 비밀번호

문제 설명

최근 DNA 분석 기술의 발달로, 유전자 정보를 기반으로 한 비밀번호 시스템이 제안되었습니다. 이 시스템에서는 일정한 길이의 DNA 서열이 비밀번호로 사용됩니다. DNA는 A, T, C, G의 4가지 염기로 구성됩니다. 주어진 DNA 서열에서 비밀번호가 될 수 있는 부분 서열을 찾아야 합니다. 각 비밀번호는 주어진 규칙에 따라 유효성을 확인해야 합니다. 특정 염기의 최소 등장 횟수와 최대 등장 횟수를 요구합니다.

문제

주어진 문자열 DNA와 각 염기(A, T, C, G)의 최소 및 최대 등장 횟수를 기준으로, 유효한 비밀번호의 개수를 세는 프로그램을 작성하시오.

입력 형식

• 첫 번째 줄에는 DNA 문자열이 주어진다. (1 ≤ DNA.length ≤ 1000)
• 두 번째 줄에는 각 염기(A, T, C, G)의 최소 등장 횟수와 최대 등장 횟수가 공백으로 구분되어 주어진다.

출력 형식

유효한 비밀번호의 개수를 출력한다.

예시

문제 해결 과정

이 문제를 해결하기 위해 다음과 같은 절차를 그대로 따릅니다.

1. 문제 분석

비밀번호의 유효성 조건을 충족해야 하므로, 부분 서열의 각 염기의 등장 횟수를 세는 방법이 필요합니다. 주어진 DNA 문자열의 모든 부분 문자열을 생성한 후, 각 부분 문자열에서 등장 횟수를 확인해야 합니다.

2. 슬라이딩 윈도우 기법

모든 부분 문자열을 검사하기에는 문자열 길이가 최대 1000이므로, 비효율적입니다. 슬라이딩 윈도우(sliding window)라는 기법을 사용하여 접근하겠습니다. 슬라이딩 윈도우는 배열이나 문자열의 일부를 나타내는 인덱스의 조합을 유지하며, 필요에 따라 왼쪽 또는 오른쪽으로 확장하고 축소합니다.

3. 구현할 방법 탐색

슬라이딩 윈도우를 사용하여 부분 서열의 길이를 조정하면서 각 염기의 카운트를 확인할 것입니다. 이 과정에서 카운트가 조건에 맞는지 확인하여 유효한 비밀번호를 카운트합니다.

4. 코드 작성

public class DNAPassword {
        public static void main(String[] args) {
            String dna = "AGCTTAGCTG";
            int[] minCounts = {1, 2, 1, 2}; // A, T, C, G의 최소 등장 횟수
            int[] maxCounts = {2, 3, 2, 3}; // A, T, C, G의 최대 등장 횟수
            
            System.out.println(validPasswordCount(dna, minCounts, maxCounts));
        }

        public static int validPasswordCount(String dna, int[] minCounts, int[] maxCounts) {
            int[] counts = new int[4]; // 각 염기에 대한 카운트
            int validCount = 0;
            int left = 0;

            for (int right = 0; right < dna.length(); right++) {
                counts[getIndex(dna.charAt(right))]++;
                
                while (isValid(counts, minCounts, maxCounts)) {
                    validCount++;
                    counts[getIndex(dna.charAt(left))]--;
                    left++;
                }
            }
            return validCount;
        }

        private static int getIndex(char c) {
            switch (c) {
                case 'A': return 0;
                case 'T': return 1;
                case 'C': return 2;
                case 'G': return 3;
                default: return -1;
            }
        }

        private static boolean isValid(int[] counts, int[] minCounts, int[] maxCounts) {
            for (int i = 0; i < 4; i++) {
                if (counts[i] < minCounts[i] || counts[i] > maxCounts[i]) {
                    return false;
                }
            }
            return true;
        }
    }

5. 테스트 및 검증

코드를 작성한 후, 위의 예시와 같은 입력값에 대해 실험해 유효한 비밀번호 개수가 올바르게 출력되는지 확인합니다. 주어진 조건을 충족하는 다양한 DNA 문자열과 카운트 값을 실험하여 프로그램의 안정성을 체크합니다.

결과 분석

실행 결과로 출력된 유효한 비밀번호의 개수는 실제로 문제에서 제공한 정답과 일치해야 합니다. 또한, 다양한 테스트 케이스를 설정해 결과가 예상과 같이 나오는지 확인합니다.

마무리

이 강좌를 통해 자바 코딩 테스트의 한 예시로 DNA 비밀번호 문제를 다뤄보았습니다. 알고리즘 문제 해결에 있어 슬라이딩 윈도우 기법이 얼마나 유용한지 이해할 수 있었기를 바랍니다. 다음 강좌에서도 유용한 알고리즘을 다루도록 하겠습니다!