BOJ_12891 : DNA 비밀번호

👉 문제링크

12891번: DNA 비밀번호

---

---

🔸 문제 분석 🔸

• 입력된 문자열 S에서 P 길이의 부분 문자열을 만들었을때, 입력된 DNA 문자열 최소 개수를 충족하는 경우의 수를 출력한다.
• 슬라이딩 윈도우 알고리즘을 이용해서 P길이의 부분 문자열을 문자열 S의 시작점부터 오른쪽으로 밀어간다.
  • 윈도우에서 벗어나는 인덱스는 현재 상태에서 빼기
  • 윈도우에 새로 들어오는 인덱스는 현재 상테에 더하기
  • 조건에 충족 하는지 확인해서 카운트

🔸 코드 🔸

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

public class Main {
    static int arr[], now[];

    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());
        String dna = br.readLine();
        arr = new int[4];
        now = new int[4];

        // 체크 배열 입력 받기
        st= new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        // 현재 상태 배열과 초기화
        for (int i = 0; i < p; i++){ now[idx(dna.charAt(i))]++; }

        int answer = check() ? 1:0;

        // 윈도우 이동
        for (int i = 1; i <= s - p; i++){
            now[idx(dna.charAt(i-1))]--;
            now[idx(dna.charAt(i+p-1))]++;
            if (check())
                answer++;
        }
        System.out.println(answer);
    }

    // 문자의 DNA 인덱스 위치
    private static int idx(char c){
        if (c == 'A')
            return 0;
        else if (c == 'C') {
            return 1;
        }
        else if (c == 'G') {
            return 2;
        }
        else if (c == 'T') {
            return 3;
        }
        return 0;
    }

    // 체크 배열과 현재 상태 배열 비교
    private static boolean check(){
        boolean flag = true;
        for (int i = 0; i < 4; i++){
            if (now[i] < arr[i]){
                flag = false;
                break;
            }
        }
        return flag;
    }
}

🔸 코드 해석 🔸

• 메소드에서 공용으로 사용하기 위해 상태 배열 arr와 현재 상태 배열 now를 정적 변수로 선언해둔다.
• 메소드 idx()에서 문자가 배열arr의 몇 번재 인덱스인지 반환한다.
• 메소드 check() 에서 배열 arr와 now가 같은지 비교해서 결과를 반환한다.
• main() 메소드에서 문제 조건의 입력을 받고, 윈도우를 이동하며 조건에 부합한 경우를 카운트한다.

---

🔸 end 🔸

• 교재 공부로 접한 문제인데, 슬라이딩 윈도우 알고리즘은 유용한 것 같다.