[코딩테스트] 백준 12891 자바

백준 12891

백준 12891 문제

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

public class Boj12891 {

    static int[] checkArr = new int[4]; // 필요한 DNA 문자 최소 개수
    static int[] currentArr = new int[4]; // 현재 윈도우의 DNA 문자 개수

    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[] str = br.readLine().toCharArray(); // 문자열을 문자 배열로 받기
        int result = 0; // 결과

        // 필요한 DNA 문자 최소 개수 초기화
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < checkArr.length; i++) {
            checkArr[i] = Integer.parseInt(st.nextToken());
        }

        // 초기 윈도우 초기화
        for (int i = 0; i < p; i++) {
            add(str[i]);
        }
        if (check()) result++; // 초기 윈도우에 정답이 있으면 카운트 올리기

        // 슬라이딩 윈도우
        for (int j = p; j < s; j++) {
            int i = j - p;
            add(str[j]);
            remove(str[i]);
            if (check()) result++;
        }

        System.out.println(result);
    }

    // 들어오는 문자에 따라 현재 윈도우의 DNA 문자 개수 더하기
    private static void add(char c) {
        if (c == 'A') currentArr[0]++;
        if (c == 'C') currentArr[1]++;
        if (c == 'G') currentArr[2]++;
        if (c == 'T') currentArr[3]++;
    }

    // 들어오는 문자에 따라 현재 윈도우의 DNA 문자 개수 빼기
    private static void remove(char c) {
        if (c == 'A') currentArr[0]--;
        if (c == 'C') currentArr[1]--;
        if (c == 'G') currentArr[2]--;
        if (c == 'T') currentArr[3]--;
    }

    // 현재 윈도우가 조건에 충족하는지 검사
    private static boolean check() {
        for (int i = 0; i < checkArr.length; i++) {
            if (currentArr[i] < checkArr[i]) {
                return false;
            }
        }
        return true;
    }
}

풀이

1. 배열을 한 칸씩 이동하면서 같은 길이의 배열의 값들을 비교하기에 O(n) 시간 복잡도를 가진 슬라이딩 윈도우 알고리즘을 사용하는 것이 적합하다.
2. 필요한 DNA 문자 최소 개수를 담는 checkArr 배열을 선언한다.
3. 현재 윈도우의 DNA 문자 개수를 담는 currentArr 배열을 선언한다.
4. 최대 1백만까지의 길이를 가진 문자열이 입력될 수 있기에 BufferedReader를 사용한다.
5. 문자열의 길이를 s로 받는다.
6. 윈도우의 길이를 p로 받는다.
7. 입력된 문자열을 toCharArray() 메서드로 문자 배열로 변환한다.
8. DNA 문자는 4개이므로 4번 반복하면서 checkArr를 초기화한다.
9. 들어오는 문자에 따라 현재 윈도우의 DNA 문자 개수 더하는 add() 메서드를 선언한다.
10. 들어오는 문자에 따라 현재 윈도우의 DNA 문자 개수 빼는 remove() 메서드를 선언한다.
11. 현재 윈도우가 조건에 충족하는지 검사하는 check() 메서드를 선언한다.
12. p만큼 반복하면서 add() 메서드를 사용해서 currentArr 초기 윈도우를 초기화한다.
13. currentArr를 초기화 한 다음 해당 윈도우에 정답이 있으면 result의 개수를 증가시켜준다.
14. 윈도우를 한칸씩 이동시키면서 맨 앞의 값은 remove() 메서드를 활용하여 currentArr값을 변경하고, 맨 뒤의 값은 add() 메서드를 활용하여 currentArr값을 변경한다.
15. 이동 후에는 checkArr와 currentArr를 비교하여 조건에 충족하면 result를 증가시킨다.
16. str의 끝까지 오면 최종 result를 출력한다.