[백준] 12891번 - DNA 비밀번호 (Java)(○)

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

12891번: DNA 비밀번호

 

<입력범위>

S : 문자열 길이 : 1 ~ 1,000,000

P : 비밀번호 길이 : 1 ~ 1,000,000

 

<풀이>

1. DNA 문자 배열에서 첫 요소부터 i ~ +P 만큼 인덱스를 넘겨줘서 패스워드로 유효한지 체크

 

<구현 #1>

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

public class Main {
    static int S, P;
    static int A, C, G, T;
    static char DNA[];
    static int PASS[] = new int[4];
    static int TMP[] = new int[4];

    int checkPass(int start, int end) {
        int ret = 0;
        for (int i=start; i<end; i++) {
            if (DNA[i] == 'A') {
                TMP[0]--;
            } else if (DNA[i] == 'C') {
                TMP[1]--;
            } else if (DNA[i] == 'G') {
                TMP[2]--;
            } else if (DNA[i] == 'T') {
                TMP[3]--;
            }
        }
        for (int x : TMP) {
            if (x != 0) return 0;
        }
        return 1;
    }
	void Solve() {
        int count = 0;
        for (int i=0; i<=S-P; i++) {
            TMP = PASS.clone();
            count += checkPass(i, i+P);
        }
        System.out.println(count);
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        StringTokenizer st = new StringTokenizer(br.readLine());
        S = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        DNA = new char[S];
        DNA = br.readLine().toCharArray();
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<4; i++) {
            PASS[i] = Integer.parseInt(st.nextToken());
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }

}

 

<풀이 #2>

1. 슬라이딩 윈도우 알고리즘을 사용해서 풀어보자.

2. 특정 범위만큼 윈도우를 잡아서 한 칸씩 이동하며 현새 상태 배열을 업데이트 한다.

3. 현재 상태 배열을 업데이트 한 이후에는 비밀번호 체크 배열과 비교하여 비밀번호 유효성을 판단한다.

4. 현재 상태 배열을 업데이트 할 때는 빠지는 문자열, 추가되는 문자열만 업데이트 하는 방식으로 진행한다.

 

※ 슬라이딩 윈도우 

1. 처음 윈도우 범위를 정하면 그 안의 요소들을 먼저 처리한다.

2. 그 다음 한칸씩 움직이면서 한 개 추가하고, 한 개 제거하면서 값을 업데이트 한다.

 

<구현 #2>

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

public class Main {
    static int S, P;
    static int checkResult = 0;
    static char DNA[];
    static int PW[] = new int[4];
    static int ST[] = new int[4];

	// 값을 추가할 때마다 호출하는 함수
    void Add(char c) {
        // 최소개수가 같아질 때만 checkResult를 업데이트 한다
        switch (c) {
        case 'A':
            ST[0]++;
            if (ST[0] == PW[0])
                checkResult++;
            break;
        case 'C':
            ST[1]++;
            if (ST[1] == PW[1])
                checkResult++;
            break;
        case 'G':
            ST[2]++;
            if (ST[2] == PW[2])
                checkResult++;                
            break;
        case 'T':
            ST[3]++;
            if (ST[3] == PW[3])
                checkResult++;                
            break;
        }
    }

	// 값을 제거할 때마다 호출하는 함수
    void Remove(char c) {
        switch (c) {
        case 'A':
            if (ST[0] == PW[0])
                checkResult--;
            ST[0]--;
            break;
        case 'C':
            if (ST[1] == PW[1])
                checkResult--;
            ST[1]--;
            break;
        case 'G':
            if (ST[2] == PW[2])
                checkResult--;
            ST[2]--;
            break;
        case 'T':
            if (ST[3] == PW[3])
                checkResult--;
            ST[3]--;
            break;
        }
    }
    
	void Solve() {
        int count = 0;
        // 1. 처음 윈도우 범위 부분 처리
        for (int i=0; i<P; i++) {
            Add(DNA[i]); //모든 문자열이 처음이니까 다 밀어넣음
        }
        // 0~P 범위의 문자열이 유효성 검증을 통과하면 count 증가시킴
        if (checkResult == 4) count++;

        // 2. 슬라이딩 윈도우 처리 부분
        for (int i=P; i<S; i++) {
            int j = i - P; // i: 추가 인덱스, j: 삭제 인덱스
            Add(DNA[i]); // 새 문자 추가
            Remove(DNA[j]); // 지나간 문자 제거
            if (checkResult == 4) count++;
        }
        System.out.println(count);
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        StringTokenizer st = new StringTokenizer(br.readLine());
        S = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        DNA = new char[S];
        DNA = br.readLine().toCharArray();
        PW = new int[4];
        ST = new int[4];
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<4; i++) {
            PW[i] = Integer.parseInt(st.nextToken());
            if (PW[i] == 0) checkResult++; // 0인부분은 먼저 증가시킴
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}