[Algorithm] 백준_DNA 비밀번호_12891번 (JAVA) 슬라이딩 윈도우

📝문제

https://www.acmicpc.net/problem/12891

DNA 비밀번호_12891번

티어: 실버 2

평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다.

하지만 민호는 이러한 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열의 부분문자열을 뽑았을 때 “AAAA”와 같이 보안에 취약한 비밀번호가 만들어 질 수 있기 때문이다. 그래서 민호는 부분문자열에서 등장하는 문자의 개수가 특정 개수 이상이여야 비밀번호로 사용할 수 있다는 규칙을 만들었다.

임의의 DNA문자열이 “AAACCTGCCAA” 이고 민호가 뽑을 부분문자열의 길이를 4라고 하자. 그리고 부분문자열에 ‘A’ 는 1개 이상, ‘C’는 1개 이상, ‘G’는 1개 이상, ‘T’는 0개 이상이 등장해야 비밀번호로 사용할 수 있다고 하자. 이때 “ACCT” 는 ‘G’ 가 1 개 이상 등장해야 한다는 조건을 만족하지 못해 비밀번호로 사용하지 못한다. 하지만 “GCCA” 은 모든 조건을 만족하기 때문에 비밀번호로 사용할 수 있다.

민호가 만든 임의의 DNA 문자열과 비밀번호로 사용할 부분분자열의 길이, 그리고 {‘A’, ‘C’, ‘G’, ‘T’} 가 각각 몇번 이상 등장해야 비밀번호로 사용할 수 있는지 순서대로 주어졌을 때 민호가 만들 수 있는 비밀번호의 종류의 수를 구하는 프로그램을 작성하자. 단 부분문자열이 등장하는 위치가 다르다면 부분문자열이 같다고 하더라도 다른 문자열로 취급한다.

---

💡풀이

문제 유형

슬라이딩 윈도우

 

걸린 시간

100분

 

시간 복잡도

O(S)

 

풀이 방법 도출

1. 슬라이딩 윈도우 알고리즘이란 창문을 미는 것과 같이 배열 내 똑같은 크기를 옆으로 밀어 제거되는 값과 추가되는 값을 고려하여 계산한다.
2. 우선 슬라이딩 윈도우는 "연속된" 부분배열을 고르는 경우 사용한다.
3. 이 문제에서도 임의의 문자열 중 부분 문자열을 골라내는 것이므로 슬라이딩 윈도우를 사용하는 것이 효율적이다.
4. 슬라이딩 윈도우와 투포인터 비교를 많이 하던데, 투포인터는 가변 길이, 슬라이딩 윈도우는 고정 길이 라는 차이점이 있다.
5. 초기 윈도우를 0부터 P-1까지 설정 한 후
6. start = 0, end = P로 설정한다.
7. 반복문을 돌려 새로 추가 된 문자 end번째 문자에 대해 카운트를 올려주고
8. 삭제 되는 문자 start번째 문자에 대해 카운트를 내려준다.
9. 이 과정을 반복하고 end가 S가 되면 반복문을 빠져나온다.

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int S = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());
        String str = br.readLine();
        char[] dna = str.toCharArray();
        int[] acgt = new int[4];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            acgt[i] = Integer.parseInt(st.nextToken());
        }

        int answer = 0;

        char[] ch = {'A', 'C', 'G', 'T'};
        int[] count = new int[4];

        //초기 윈도우 설정
        for (int i = 0; i < P; i++) {
            for (int j = 0; j < 4; j++) {
                if (dna[i]==ch[j]) {
                    count[j]++;
                }
            }
        }

        int start = 0;
        int end = P;

        while (true) {
            //최소개수 이상이라면
            if (acgt[0] <= count[0] && acgt[1] <= count[1] && acgt[2] <= count[2] && acgt[3] <= count[3]) {
                answer++;
            }
            if(end == S) break;
            //슬라이딩 윈도우: 오른쪽으로 한칸 이동 후 이동 후 개수를 늘려줌
            for (int i = 0; i < 4; i++) {
                if (dna[end]==ch[i]) { //새로 추가된 문자
                    count[i]++;
                }
                if (dna[start]==ch[i]) { //제거된 문자
                    count[i]--;
                }
            }

            start++;
            end++;
        }
        System.out.println(answer);
    }
}

---

🤔Review

슬라이딩 윈도우..얼마전 코테를 풀고 올솔이라 생각하고 기분좋게 시간도 남기고 나왔는데 알고보니 내가 문제를 잘못읽은 포인트들이 몇가지 있더라 근데 사람들이 슬라이딩 윈도우로 풀었다길래, 난 제대로 읽었어도 슬라이딩 윈도우 개념을 몰랐으니까 못풀었을듯? ^^ 오늘도 새로운 알고리즘을 배워갑니다,🫡