백준/12891번/Java - DNA 비밀번호

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

12891번: DNA 비밀번호

---

슬라이딩 윈도우를 활용하는 문제이다.

문제에서 주어진 길이 S의 문자열을 P만큼 잘라서 주어진 조건( 각 문자 A, C, G, T의 최소 개수)를 만족하는지 판별하면 된다.

S와 P의 범위가 최대 1,000,000만큼 주어졌기 때문에

P만큼 자른 문자열 전체를 매번 조건에 맞는지 검사하게 되면 시간초과가 발생한다.

잘라낸 문자열의 시작 인덱스와 종료 인덱스는 각각 0, P-1에서 시작하여 조건 검사 이후 마다 1씩 증가하므로,

맨 처음 검사 이후에는 반복문을 돌면서 맨 앞 문자와 맨 뒤 문자만 달라진다는 점을 활용하면 시간을 단축할 수 있다.

 

맨 처음, 잘라낸 문자열에서 각 문자별 개수를 배열에 저장한다.

그 이후 반복문에서는 문자열에서 빠지게 되는 맨 앞 문자, 새로 문자열에 들어오는 맨 뒤 문자에 따라 문자별 개수 배열을 변경 한 뒤, 조건에 맞는 지 검사하면 된다.

이렇게 하면 매번, 잘라낸 문자열을 돌면서 조건을 검사할 필요가 없어진다.

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


public class Main {
    static int[] count;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int S = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());

        String dna = br.readLine();
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[4];
        for(int i=0; i<4; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int start = 0, end = start+P-1;
        int answer = 0;

        count = new int[4];
        for(int i=start; i<=end; i++) {
            char c = dna.charAt(i);
            if(c == 'A') {
                count[0]++;
            }
            else if(c == 'C') {
                count[1]++;
            }
            else if(c == 'G') {
                count[2]++;
            }
            else {
                count[3]++;
            }
        }
        if(checkCount(arr)) answer++;

        while(end<S-1) {
            char oldStart = dna.charAt(start);
            remove(oldStart);
            start++;
            end++;
            char newEnd = dna.charAt(end);
            add(newEnd);
            if(checkCount(arr)) answer++;
        }



        bw.write(""+answer);
        br.close();
        bw.flush();
        bw.close();
    }
    private static void add(char c){
        switch (c){
            case 'A':
                count[0]++;
                break;
            case 'C':
                count[1]++;
                break;
            case 'G':
                count[2]++;
                break;
            case 'T':
                count[3]++;
                break;
        }
    }
    private static void remove(char c){
        switch (c){
            case 'A':
                count[0]--;
                break;
            case 'C':
                count[1]--;
                break;
            case 'G':
                count[2]--;
                break;
            case 'T':
                count[3]--;
                break;
        }
    }
    private static boolean checkCount(int[] arr) {
        if(arr[0] > count[0]) return false;
        else if(arr[1] > count[1]) return false;
        else if(arr[2] > count[2]) return false;
        else if(arr[3] > count[3]) return false;
        return true;
    }
}

checkCount로 검사하지 않고 조건에 만족하는 문자의 개수를 변수로 선언해 해당 변수가 4를 만족하는지 검사하는 방법도 있다.

(인프런 Do it! 알고리즘 코딩테스트 강의 참고)

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


public class Main {
    static int[] arr;
    static int[] count;
    static int passCount = 0; //최소 개수를 만족하는 문자의 수 (4가 되면 모든 문자가 조건을 만족하는 것)
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int S = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());

        String dna = br.readLine();
        st = new StringTokenizer(br.readLine());
        arr = new int[4];
        for(int i=0; i<4; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            if(arr[i] == 0) passCount++; // 최소 개수가 0개면 무조건 통과하므로 passCount++
        }

        int answer = 0;
        count = new int[4];
        for(int i=0; i<P; i++) {
            char c = dna.charAt(i);
            add(c);
        }

        if(passCount == 4) answer++;

        for(int end=P; end<S; end++) {
            int start = end - P;
            remove(dna.charAt(start));
            add(dna.charAt(end));
            if(passCount == 4) answer++;
        }

        bw.write(""+answer);
        br.close();
        bw.flush();
        bw.close();
    }
    private static void add(char c){
        switch (c){
            case 'A':
                count[0]++;
                if(arr[0] == count[0]) passCount++; //조건을 만족하는 문자가 생긴것이므로 passCount 1 증가함.
                break;
            case 'C':
                count[1]++;
                if(arr[1] == count[1]) passCount++;
                break;
            case 'G':
                count[2]++;
                if(arr[2] == count[2]) passCount++;
                break;
            case 'T':
                count[3]++;
                if(arr[3] == count[3]) passCount++;
                break;
        }
    }
    private static void remove(char c){
        switch (c){
            case 'A':
                if(arr[0] == count[0]) passCount--; // 조건에 맞는 문자가 조건에 맞지 않게 되므로 passCount 1 감소
                count[0]--;
                break;
            case 'C':
                if(arr[1] == count[1]) passCount--;
                count[1]--;
                break;
            case 'G':
                if(arr[2] == count[2]) passCount--;
                count[2]--;
                break;
            case 'T':
                if(arr[3] == count[3]) passCount--;
                count[3]--;
                break;
        }
    }
}