백준 12891_DNA 비밀번호_JAVA

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

12891번: DNA 비밀번호

 

처음 풀었던 시간초과 코드

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

public 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());

        char[] charArr = br.readLine().toCharArray();

        int[] check = new int[4];

        st = new StringTokenizer(br.readLine());

        for(int i=0; i<4; i++) {
            check[i] = Integer.parseInt(st.nextToken());
        }

        int start = 0;
        int end = p-1;
        int count = 0;

        while (end<s) {
            int checkA = 0;
            int checkC = 0;
            int checkG = 0;
            int checkT = 0;

            for(int i=start; i<=end; i++) {
                if (charArr[i] == 'A') {
                    checkA += 1;
                } else if (charArr[i] == 'C') {
                    checkC += 1;
                } else if (charArr[i] == 'G') {
                    checkG += 1;
                } else if (charArr[i] == 'T') {
                    checkT += 1;
                }
            }
            if (checkA != check[0]) {
                start += 1;
                end += 1;
                continue;
            } else if (checkC != check[1]) {
                start += 1;
                end += 1;
                continue;
            } else if (checkG != check[2]) {
                start += 1;
                end += 1;
                continue;
            } else if (checkT != check[3]) {
                start += 1;
                end += 1;
                continue;
            }
            count += 1;
            start += 1;
            end += 1;
        }
        System.out.print(count);
    }
}

 

 

윈도우 슬라이드를 공부하고 수정한 코드

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

public class Main {
    static int[] myCheck;
    static int[] check;
    static int checkAnswer;
    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()); // 부분 문자열 길이

        char[] dna = br.readLine().toCharArray(); // DNA 배열

        check = new int[4]; // dna 조건 배열
        myCheck = new int[4]; // 지금 비밀번호 체크 배열
        checkAnswer = 0; // 4가지의 조건을 만족하는지 count하는 int
        int count = 0; // 정답 갯

        st = new StringTokenizer(br.readLine());

        // check 배열에 입력 받은 조건 대입
        for (int i = 0; i < 4; i++) {
            check[i] = Integer.parseInt(st.nextToken());
            if (check[i] == 0) {
                checkAnswer++;
            }
        }

        // 제일 처음부터 부분집합 갯수까지 알파벳 세기
        for (int i = 0; i < P; i++) {
            Add(dna[i]);
        }

        if (checkAnswer == 4) {
            count++;
        }

        // 윈도우 슬라이딩
        for (int i = P; i<S; i++) {
            int j = i-P; // j가 부분집합의 가장 처음 단어, i가 부분집합이 끝나고 가장 처음 단어
            Add(dna[i]); // i를 추가하고 계산
            Remove(dna[j]); // j를 빼주고 계산

            if (checkAnswer==4) {
                count++;
            }
        }

        System.out.print(count);
        br.close();
    }

    private static void Add(char c) {
        switch(c) {
            case 'A':
                myCheck[0]++;
                if (myCheck[0] == check[0]) {
                    checkAnswer++;
                }
                break;
            case 'C':
                myCheck[1]++;
                if (myCheck[1] == check[1]) {
                    checkAnswer++;
                }
                break;
            case 'G':
                myCheck[2]++;
                if (myCheck[2] == check[2]) {
                    checkAnswer++;
                }
                break;
            case 'T':
                myCheck[3]++;
                if (myCheck[3] == check[3]) {
                    checkAnswer++;
                }
                break;
        }
    }

    private static void Remove(char c) {
        switch(c) {
            case 'A':
                // 빼기 전 상황에서 두가지의 check가 같으면
                // 조건이 성립하지 않기 때문에 checkAnswer을 하나 빼준다
                if (myCheck[0] == check[0]) {
                    checkAnswer--;
                }
                myCheck[0]--;
                break;
            case 'C':
                if (myCheck[1] == check[1]) {
                    checkAnswer--;
                }
                myCheck[1]--;
                break;
            case 'G':
                if (myCheck[2] == check[2]) {
                    checkAnswer--;
                }
                myCheck[2]--;
                break;
            case 'T':
                if (myCheck[3] == check[3]) {
                    checkAnswer--;
                }
                myCheck[3]--;
                break;
        }
    }
}

 

 

 

회고

- 윈도우 슬라이드 코드 짜기가 너무 생소해서 2시간은 잡고 있었던 것 같지만 결국 이해하고 해결해서 다행이다.