[백준 알고리즘 - 12891] DNA 비밀번호 - 자바 [With Java]

12891번: DNA 비밀번호 (acmicpc.net)

12891번: DNA 비밀번호

 

 

 

 

 

 

 

 

 

[해설]

 

이 문제의 경우 조금 까다로운 문제입니다.

 

일단 문제를 분석 해봅시다.

 

1. 입력 값 4 2를 입력 했을때

 

입력 값 4의 의미는 4개의 문자열을 입력 값으로 받는다는 뜻이 됩니다.

즉 GATA라는 문자열을 받으면 4개의 문자열로 받는다는 뜻입니다.

 

2의 의미는 GATA라는 문자열이 나온다면

 

GA    AT   TA즉 이렇게 문자열을 두 개씩 잘라서 확인 한다는 의미가 됩니다.

 

 

이렇게 GA를 한번 보고

 

 

이렇게 AT를 한번 보고

 

 

TA를 보고 총 3번을 보는 것 입니다.

 

이유는 문자열 4 개 중 2개씩 본다고 했음으로 2개의 문자열을 앞으로 나가면서 보는 것이 이 문제의 키 포인트 입니다.

이것이 윈도우 슬라이딩 입니다.

 

그렇다면 한번 생각을 해봅시다.

 

 

 

 

비밀번호 1 0 0 1을 입력 받았을 때

GA 

AT

TA 로 세번 총 확인 했을때 비밀번호가 맞는 경우는 몇번인가? 라고 물어봅니다.

 

그렇다면 GA를 먼저 확인 해봅시다

 

 

여기에 설명을 본다면 

 

문자열의 비밀번호 순서는 A C G T라고 했습니다.

그러면 

A    C    G    T 

0    0     0     0

 

이런식으로 초기 비밀번호가 설정 될 것 입니다.

 

그러면 처음에 GA를 확인 한다 했으니 GA는 비밀번호가 어떻게 될까요?

 

A    C    G    T

0    0     0     0  이 부분에서 GA가 들어오면 1씩 증가 한다 했음으로

 

A    C    G    T       <--- GA

1    0     1    0

 

 

1    0      0    1    <--- 입력 값 비밀번호 

 

즉 처음 GA가 들어올때는 비밀번호가 1 0 1 0 이 될 것 입니다.

 

하지만 입력 값의 비밀번호는 1 0 0 1이죠.

그렇다면 이 비밀번호는 틀린 비밀번호 입니다.

 

그렇다면 AT를 보시죠

 

A    C    G    T       <--- AT

1    0     0     1

 

 

1    0      0    1    <--- 입력 값 비밀번호 

 

AT는 1 0 0 1 임으로 비밀번호 1 0 0 1과 같습니다.

그렇다면 값을 1 추가 시킵니다.

 

그 후 

TA도 봅시다.

 

TA는

A    C    G    T

1    0     0     1

임으로

 

들어온 비밀번호가 1 0 0 1임으로 비밀번호가 맞기 때문에 값을 1 증가 시킵니다.

 

그렇다면 총 값은 2가 됩니다.

 

 

예제 출력을 본다면 값이 2임으로 이렇게 푸는 것이 맞겠네요.

 

[코드로 작성]

 

그렇다면 코드로는 어떻게 작성해야 할까요?

 

일단 여러가지 방법이 있지만 가장 쉬운 방법은

 

 비밀번호가 들어온 1 0 0 1을 보는 것 입니다.

 

A    C    G    T

1    0     0     1

 

로 되어있습니다.

그렇다면 이 비밀번호가 필요한 문자열은 A T 딱 두개 밖에 필요가 없죠?

그러면 C 와 G는  0임으로 비밀번호를 확인 할 필요가 없습니다.

 

A와 T만 1임으로 A와 T의 문자열만 들어오면 값이 맞는 것이 되는거죠

 

그렇다면 비밀번호는 반드시  4개입니다.

 

비밀번호가 1 0 0 1로 들어왔습니다.

그렇다면 0이 들어올때는 값을 확인 할 필요가 없음으로 count++를 해주는 것 입니다.

 

그리고 문자열 A 와 T가 들어오면 count++를 해줘서

 

count가 4개가 된다면 값을 1을 증가 시키는 것 입니다.

 

자 아직 이해가 되지 않습니다.

 

다시 한번 보도록 하겠습니다.

 

 

 

처음에 GA가 들어왔습니다.

 

입력 값의 비밀번호는  1 0 0 1 입니다. A와 T가 필요한 상황입니다.

 

위에서 말한 것 처럼 비밀번호가 1 0 0 1이 들어온다면

 

0이 들어올떄마다 count++를 해줘라고 했습니다.

그렇다면 기본 count의 값은 2입니다.

 

그 후 GA의 값과 하나씩 비교 해보는 것 입니다.

A    C    G      T

1    0      0     1

1    0     1      0

 

이렇게 될 것 입니다.

그렇다면 각 배열인덱스 끼리 값이 같다면 count++를 해주는 것 입니다.

 

그렇게 된다면 0은 이미 count를 셋기 때문에 세어주지 않고

 A의 값만 같기 때문에 count++를 해줍니다.

 

결과 값은 count = 3이 되겠네요.

 

제가 위에서 말했듯이 count = 4가 된다면 결과 값을 1을 올리라고 설정 해놨음으로

4가 되지 않음으로 fasle입니다.

 

여기서 중요 합니다.

 

 

 

저희는 이제 GA란 비밀번호를 확인했습니다.

 

그렇다면 다음의 확인 할 것은 AT 일 것 입니다.

 

여기서 중요한 점이 있습니다.

 

 

GA와 AT를 비교한다면 중간에 걸리는 값인 A가 있습니다.

 

이미 GA에서 검증을 했는데도 AT에서도 또 A를 검증합니다.

 

이렇게 할필요가 있을까요?

 

문제의 값은 최대  1,000,000이 들어온다고 했음으로

 

시간 초과가 날 수 있는 상황입니다.

 

그렇기 때문에 윈도우 슬라이딩의 기술을 써서

 

GA를 확인 했기 때문에 A를 확인 하지 않고

 

T만 확인 하게만 하면 되는것이죠.

 

그렇다면 또 TA를 확인할떄는

 

T를 확인 할 필요 없이 다시 A만 확인하고 이런식으로 확인 하는 것 입니다.

 

 

package com.algorithm;

import ch.qos.logback.core.subst.Tokenizer;

import java.util.*;
import java.io.*;
public class Main{
    static int[] PassWord = new int[4]; // 입력값 비밀번호 1 0 0 1
    static int[] MyPassWord = new int[4]; // GATA문자열이 들어오면 짤라서 확인 GA,TA,AT
    static int count;
    public static void main(String[] args) throws IOException {
        int result = 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int length = Integer.parseInt(st.nextToken()); // 총 문자열길이 4
        int range = Integer.parseInt(st.nextToken()); // 문자열 범위 2
        char[] Dna;
        Dna = br.readLine().toCharArray(); // GATA문자열이 들어옴
        st = new StringTokenizer(br.readLine()); // 1 0 0 1 비밀번호 저장.
        for(int i=0; i<4;i++){
            PassWord[i] = Integer.parseInt(st.nextToken()); // 1 0 0 1 비밀번호를 PassWord배열에 넣음

            if(PassWord[i] == 0){ // 비밀번호가 1 0 0 1일때 0이 들어갈때마다 count++증가.
                count++; // 기본 카운터는 2가 될 것 임.
            }
        }


        for(int i=0; i<range;i++){ // range = 2기 때문에 2번 반복
            Add(Dna[i]); //각 배열을 비교하는 Add함수 사용
                        //GA의 경우는 1 0 1 0 임으로 1 0 0 1과 다르기때문에 count 값은 3이 됨.
        }
        if(count==4) result++;

        //이제 GA를 한번 확인 했으니
        //이 다음 확인부터는 윈도우 슬라이딩을 이용 할 것임.
        //이 FOR문은 윈도우 슬라이딩 반복문임.
        for(int j=range;j<length;j++){
            int start = j-range;
            int end = j;
            Add(Dna[end]); //GA를 위에서 검증했고 AT를 검증할 차례 하지만 A는 이미 검증되었음으로 확인 X
                           //Add(T)

            Remove(Dna[start]); //윈도우 슬라이딩임으로 GA -> AT로 넘어가야 하기 떄문에 G의 값을 삭제 시켜준다.
            if(count==4) result++;
        }
        System.out.println(result);
    }
    public static void Remove(char c){

        switch(c){
            case 'A': {
                if(MyPassWord[0]==PassWord[0]){
                    count--;
                }
                MyPassWord[0]--;
                break;
            }
            case 'C': {
                if(MyPassWord[1]==PassWord[1]){
                    count--;
                }
                MyPassWord[1]--;
                break;
            }
            case 'G':{
            //GA값은 1 0 1 0 이였다. 1 0 0 1 값과 비교한다.
            //G의 자리 수를 서로 비교함. 1 , 0임으로 if는 false  

                if(MyPassWord[2]==PassWord[2]){
                    count--;
                }
                MyPassWord[2]--;
                break;
            }
            case 'T':{


                if(MyPassWord[3]==PassWord[3]){
                    count--;
                }
                MyPassWord[3]--;
                break;
            }
        }

    }
    public static void Add(char c){ //GA , AT , TA가 들어올 것 임.

        switch(c){
            case 'A':{
                MyPassWord[0]++;
                if(MyPassWord[0]==PassWord[0]) {
                    count++;
                }
                break;
            }
            case 'C':{
                MyPassWord[1]++;
                if(MyPassWord[1]==PassWord[1]){
                    count++;
                }
                break;
            }
            // 0 0 0 0과 1 0 0 1 비밀번호 비교
            case 'G':{
                MyPassWord[2]++;
                //G가 들어오면 G자리에 1을 추가.
                //그 후 비밀번호가 자리 값이 같은지 비교
                if(MyPassWord[2]==PassWord[2]){
                    count++;
                }
                break;
            }
            case 'T':{
                MyPassWord[3]++;
                if(MyPassWord[3]==PassWord[3]){
                    count++;
                }
                break;
            }
        }
    }
}

 

 

 

주석에 설명을 일일이 설명을 다 했기 때문에 읽어본다면 이해할 거라 생각합니다.

 

이렇듯 이문제의 경우 결코 쉬운문제는 아니였던거 같습니다.