백준(12891번, DNA 비밀번호, 실버II)

문제 내용

문제 내용

---

제출한 코드

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

public class Main {
    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 length = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());

        // DNA 문자열 S
        String S = br.readLine();

        // 각 문자의 최소 개수
        st = new StringTokenizer(br.readLine());
        int[] minCounts = new int[4];
        for (int i = 0; i < 4; i++) {
            minCounts[i] = Integer.parseInt(st.nextToken());
        }

        // 현재 문자 개수
        int[] currentCounts = new int[4];
        for (int i = 0; i < P; i++) {
            addCount(S.charAt(i), currentCounts);
        }

        // 유효한 비밀번호
        int validCount = 0;
        if (isValid(minCounts, currentCounts)) {
            validCount++;
        }

        // 슬라이딩 윈도우
        for (int i = P; i < length; i++) {

            addCount(S.charAt(i), currentCounts);
            removeCount(S.charAt(i - P), currentCounts);

            if (isValid(minCounts, currentCounts)) {
                validCount++;
            }
        }

        bw.write(String.valueOf(validCount));
        bw.newLine();

        bw.flush();
        br.close();
        bw.close();
    }

    private static void addCount(char c, int[] counts) {
        switch (c) {
            case 'A': counts[0]++; break;
            case 'C': counts[1]++; break;
            case 'G': counts[2]++; break;
            case 'T': counts[3]++; break;
        }
    }

    private static void removeCount(char c, int[] counts) {
        switch (c) {
            case 'A': counts[0]--; break;
            case 'C': counts[1]--; break;
            case 'G': counts[2]--; break;
            case 'T': counts[3]--; break;
        }
    }

    private static boolean isValid(int[] minCounts, int[] currentCounts) {
        for (int i = 0; i < 4; i++) {
            if (currentCounts[i] < minCounts[i]) {
                return false;
            }
        }
        return true;
    }
}

---

후기

해당 문제는 코드부터 작성을 해보기가 너무 어려워서
저번 주차때 상효랑 애들이 얘기했던 내용이 떠올라서 일단 수도코드 형식으로 먼저 작성을 해봤다

1. 첫 번째 줄에 DNA 문자열의 길이(S)와 부분 문자열의 길이(P)를 입력받는다.
2. 두 번째 줄에 DNA 문자열(S)을 입력받는다.
3. 세 번째 줄에 각 문자의 최소 요구 개수(A, C, G, T 순서)를 입력받는다.

위 부분까지는 문제가 없었지만, 배열을 초기화를 해줘야하는데 그냥 초기화가 아닌, 길이 P만큼의 첫 번째 부분 문자열에서 각 문자의 개수를 계산하여 현재 개수를 저장하여 초기화를 해줬어야됐기에 다음 부분에서 어려워서 막혔다

해당 문제를 제일 오래 고민을 해보다가, 구글링을 했는데 슬라이딩 윈도우를 알지 못하면 시간 초과가 발생해 풀지 못하는 걸로 이해했다 

---

슬라이딩 윈도우 개념

슬라이딩 윈도우에 대해 가볍게 설명하면
부분 문자열의 시작 지점을 하나씩 오른쪽으로 이동하면서 다음을 수행한다
윈도우에서 새로 추가된 문자에 대한 개수를 + , 윈도우에서 제외된 문자에 대한 개수 -, 해준뒤에 현재 개수가 최소 요구 개수를 만족하는지 확인하고 만족하면 유효한 비밀번호 개수를 증가 이런식의 로직이라고 이해해주면 될거같다

입력 DNA 문자열 길이 S와 부분 문자열 길이 P
입력 DNA 문자열 S
입력 최소 요구 개수 [A_min, C_min, G_min, T_min]

---

슬라이딩 윈도우 메서드

슬라이딩 윈도우에서 사용할 별도의 addCount, removeCount, isValid 를 설계해서 풀이하였다

int[] currentCounts = new int[4];
        for (int i = 0; i < P; i++) {
            addCount(S.charAt(i), currentCounts);
        }

        // 비밀번호의 개수 카운팅
        int validCount = 0;
        if (isValid(minCounts, currentCounts)) {
            validCount++;
        }

        for (int i = P; i < S_length; i++) {
            // 윈도우 이동
            addCount(S.charAt(i), currentCounts);
            removeCount(S.charAt(i - P), currentCounts);

            // 조건 충족 여부 확인
            if (isValid(minCounts, currentCounts)) {
                validCount++;
            }
        }

 

참고한 자료

https://plplim.tistory.com/7
https://velog.io/@richsubin/%EB%B0%B1%EC%A4%80-12891%EB%B2%88-DNA-%EB%B9%84%EB%B0%80%EB%B2%88%ED%98%B8-JAVA