[12891] DNA 비밀번호

✔ DNA 비밀번호

[백준 12891]

문제 분석하기

시간 제한은 2초이지만 P와 S의 길이가 1000000으로 매우 크기 때문에 O(n)의 시간 복잡도 알고리즘이 필요

이때 부분 문자열의 길이가 P이므로 슬라이딩 윈도우 개념을 이용

길이가 P인 윈도우를 지정하여 배열 S의 시작점에 둔 후 윈도우를 오른쪽으로 밀면서 조건에 맞는지 탐색하여 문제에 접근

손으로 풀어보기

1. S 배열과 비밀번호 체크 배열을 저장
2. 윈도우에 포함된 문자로 현재 상태 배열을 만들고, 현재 상태 배열과 비밀번호 체크 배열을 비교하여 유효 비밀번호인지 판단
3. 윈도우를 한 칸씩 이동하며 현재 상태 배열을 업데이트하고 비밀번호 유효성을 판단
   • 이때 빠지는 문자열과 신규 문자열만 보고 업데이트하는 방식으로 진행
   • 이로인해 부분 문자열의 크기가 크더라고, 1칸 이동할 때마다 2개의 데이터만 업데이트할 수 있게 됨

슈도코드 작성하기

S(문자열 크기) P(부분 문자열의 크기)
A(문자열 데이터)
charArr(비밀번호 체크 배열)
myArr(현재 상태 배열)
checkSecret(몇 개의 문자와 관련된 개수를 충족했는지 판단하는 변수)
P 범위(0 ~ P - 1)만큼 S배열에 적용하고, 유효한 비밀번호인지 판단하기
for(i를 P에서 S까지 반복)
{
    j선언(i - P)
    // 이 부분은 함수(Add, Remove)로 별도 구현하기
    한 칸씩 이동하면서 제거되는 문자열과 새로 들어오는 문자열을 처리하기
    유효한 비밀번호인지(checkSecret == 4) 판단해 결괏값에 업데이트하기
}
결괏값 출력하기

별도 함수
Add(문자 더하기 함수)
{
    새로 들어온 문자를 myArr에 업데이트하거나 checkSecret 값 변경하기
}
Remove(문자 빼기 함수)
{
    제거되는 문자를 myArr에 업데이트하거 checkSecret 값 변경하기
}

코드 구현하기

/**
 * 12891) DNA_비밀번호
 */
public class D009_12891 {
    static int checkArr[];
    static int myArr[];
    static int checkSecret;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        // S(문자열 크기) P(부분 문자열의 크기)
        int S = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());
        int Result = 0;
        // A(문자열 데이터)
        char A[] = new char[S];
        // charArr(비밀번호 체크 배열) - ACGT
        checkArr = new int[4];
        // myArr(현재 상태 배열) - ACGT
        myArr = new int[4];
        // checkSecret(몇 개의 문자와 관련된 개수를 충족했는지 판단하는 변수)
        checkSecret = 0;
        A = bf.readLine().toCharArray();
        st = new StringTokenizer(bf.readLine());
        for (int i = 0; i < 4; i++) {
            checkArr[i] = Integer.parseInt(st.nextToken());
            // 0이면 이미 그 문자열에 대해서는 충족하므로 +1
            if (checkArr[i] == 0)
                checkSecret++;
        }
        // P 범위(0 ~ P - 1)만큼 S배열에 적용하고, 유효한 비밀번호인지 판단하기
        // 초기 P 부분 문자열 처리 부분
        for (int i = 0; i < P; i++) {
            Add(A[i]);
        }
        if (checkSecret == 4)
            Result++;
        // 슬라이딩 윈도우 처리 부분
        for (int i = P; i < S; i++) {
            // 한 칸씩 이동하면서 제거되는 문자열과 새로 들어오는 문자열을 처리하기
            // i는 부분 문자열의 끝 (추가되어야 함), j는 부분 문자열의 처음 (삭제되어야 함)
            int j = i - P;
            Add(A[i]);
            Remove(A[j]);
            // 4자릿수와 관련된 크기가 모두 충족될 때 유효한 비밀번호
            if (checkSecret == 4)
                Result++;
        }
        System.out.println(Result);
        bf.close();
    }

    // 문자 더하기 함수
    private static void Add(char c) {
        // 새로 들어온 문자를 myArr에 업데이트하거나 checkSecret 값 변경하기
        switch (c) {
            case 'A':
                myArr[0]++;
                if (myArr[0] == checkArr[0]) // 추가됨으로써 조건 충족 O
                    checkSecret++;
                break;
            case 'C':
                myArr[1]++;
                if (myArr[1] == checkArr[1])
                    checkSecret++;
                break;
            case 'G':
                myArr[2]++;
                if (myArr[2] == checkArr[2])
                    checkSecret++;
                break;
            case 'T':
                myArr[3]++;
                if (myArr[3] == checkArr[3])
                    checkSecret++;
                break;
        }
    }

    // 문자 빼기 함수
    private static void Remove(char c) {
        // 제거되는 문자를 myArr에 업데이트하거 checkSecret 값 변경하기
        switch (c) {
            case 'A':
                if (myArr[0] == checkArr[0]) // 제거됨으로써 조건 충족 X
                    checkSecret--;
                myArr[0]--;
                break;
            case 'C':
                if (myArr[1] == checkArr[1])
                    checkSecret--;
                myArr[1]--;
                break;
            case 'G':
                if (myArr[2] == checkArr[2])
                    checkSecret--;
                myArr[2]--;
                break;
            case 'T':
                if (myArr[3] == checkArr[3])
                    checkSecret--;
                myArr[3]--;
                break;
        }
    }
}