백준 12891: DNA 비밀번호 (java)

알고리즘

Sliding Window

 

체감 난이도

★ ★ ★ ☆ ☆

 

다시 풀 수 있는가?

YES

 

[백준] 12891번: DNA 비밀번호 - java (tistory.com)

[백준] 12891번: DNA 비밀번호 - java

---

 

1. 이상적인 A, C, G, T 개수 배열 설정

 

A, C, G, T의 개수를 담을 배열을 만들어준다.

 

이후에 비교를 위해 이 배열에는 이상적인 개수를 저장해준다.

 

        // A C G T
        cntArr = new int[4];
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            cntArr[i] = Integer.parseInt(st2.nextToken());
        }

 

2. 초기 윈도우 설정

 

초기 윈도우 설정을 위해 P만큼 돌려주고.. cntArr2의 개수를 count 한다.

 

        // 초기 윈도우 설정
        cntArr2 = new int[4];
        for (int i = 0; i < P; i++) {
            add(arr[i]);
        }
        
        if (cntArr2[0] >= cntArr[0] && cntArr2[1] >= cntArr[1] && cntArr2[2] >= cntArr[2] && cntArr2[3] >= cntArr[3]) {
            cnt++;
        }

 

3. 다음 윈도우 설정

 

j는 끝자리, i는 앞자리로 설정해준다.

 

맨 처음 i는 j - P로, 아직 이동 전의 index를 가리키고 있다.

 

따라서, 끝(j)의 알파벳을 add 해주고, 처음(i)의 알파벳을 remove 해줘서

cntArr2 배열의 값을 조정해줌으로써 sliding window를 실현한다.

 

        for (int j = P; j < S; j++) {
            int i = j - P;
            add(arr[j]);
            remove(arr[i]);
            
            if (cntArr2[0] >= cntArr[0] && cntArr2[1] >= cntArr[1] && cntArr2[2] >= cntArr[2] && cntArr2[3] >= cntArr[3]) {
                cnt++;
            }
        }

 

4. add & remove 함수

 

    public void add(char x) {
        switch (x) {
            case 'A':
                cntArr2[0]++;
                break;
            case 'C':
                cntArr2[1]++;
                break;
            case 'G':
                cntArr2[2]++;
                break;
            case 'T':
                cntArr2[3]++;
                break;
        }
    }
    
    public void remove(char x) {
        switch (x) {
            case 'A':
                cntArr2[0]--;
                break;
            case 'C':
                cntArr2[1]--;
                break;
            case 'G':
                cntArr2[2]--;
                break;
            case 'T':
                cntArr2[3]--;
                break;
        }
    }

 

 

전체 코드 ▼

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    char[] arr;
    int[] cntArr, cntArr2;
    int cnt = 0;
    
    public void add(char x) {
        switch (x) {
            case 'A':
                cntArr2[0]++;
                break;
            case 'C':
                cntArr2[1]++;
                break;
            case 'G':
                cntArr2[2]++;
                break;
            case 'T':
                cntArr2[3]++;
                break;
        }
    }
    
    public void remove(char x) {
        switch (x) {
            case 'A':
                cntArr2[0]--;
                break;
            case 'C':
                cntArr2[1]--;
                break;
            case 'G':
                cntArr2[2]--;
                break;
            case 'T':
                cntArr2[3]--;
                break;
        }
    }
    
    public void solution() throws Exception {
        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());
        
        arr = br.readLine().toCharArray();
        
        // A C G T
        cntArr = new int[4];
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            cntArr[i] = Integer.parseInt(st2.nextToken());
        }
        
        // 초기 윈도우 설정
        cntArr2 = new int[4];
        for (int i = 0; i < P; i++) {
            add(arr[i]);
        }
        
        if (cntArr2[0] >= cntArr[0] && cntArr2[1] >= cntArr[1] && cntArr2[2] >= cntArr[2] && cntArr2[3] >= cntArr[3]) {
            cnt++;
        }
        
        for (int j = P; j < S; j++) {
            int i = j - P;
            add(arr[j]);
            remove(arr[i]);
            
            if (cntArr2[0] >= cntArr[0] && cntArr2[1] >= cntArr[1] && cntArr2[2] >= cntArr[2] && cntArr2[3] >= cntArr[3]) {
                cnt++;
            }
        }
        
        System.out.println(cnt);
    }
    
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}