백준 12891번 : DNA 비밀번호 자바

 

🧫 문제 분석

 

✔️ 출처

DNA 비밀번호 실버 2

 

📖 문제

 

 

 

투포인터 문제로 슬라이딩 윈도우에 대한 지식이 있다면

풀이방법이 쉽게 떠오를 것이다. 

 

모르겠다면 네트워크에서 흐름제어로 사용중인 슬라이딩 윈도우 에 대해서 학습해보자.

 

 

이 문제는 윈도우 역할을 할 배열을 하나 만들고,

읽어들인 비밀번호가 DNA 문자에 맞는지 확인하기 위해 각 문자마다 개수를 저장할 배열을 만든다. 

 

front 포인터와 back 포인터로 이용하되

우선 부분 문자열 p 만큼윈도우에 채우고 

만들 수 있는 DNA 비밀번호인지확인한다.

 

확인 후 새로운 문자를 받기위해  front를 뒤로 한 칸 땡겨서 윈도우의 맨 앞쪽을 빼고 

윈도우 사이즈를 1 줄인 뒤 back을 늘려서 윈도우 사이즈를 p일때까지 채운다.

 

 

p 가4라 했을 때  

 

  

 

코드에서는 back 위치에 값을 추가하고 back + 1 이 되기에 그림과 다를 수 있지만  원리는 갖다. 

코드로 보자면 front는 현재 idx = 1, back 은 idx = 5

---

🔅 문제 풀이

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 s = Integer.parseInt(st.nextToken());
        int p = Integer.parseInt(st.nextToken());
        String dnaLine = br.readLine();
        int[] dnaCheck = new int[4];

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

        // DNA 조건의 문자 기준 개수
        for (int i = 0; i < 4; i++) {
            dnaCheck[i] = Integer.parseInt(st.nextToken());
        }


        int answer = 0;
        int front = 0;
        int back = 0;
        int size = 0; // 현재 윈도우의 크기
        int[] check = new int[4]; // 현재 윈도우의 상태를 가진 배열

        while (back < s ) {
            int idx = findIdx(dnaLine.charAt(back));

            // 윈도우의 크기가 작다면 더 채운다.
            if (size < p) {
                if (idx >= 0 ) check[idx]++;
                size++;
                back++;

                // 윈도우 크기가 p와 같다면 비밀번호 체크 후 맨 앞쪽 단어를 빼고 사이즈를 줄인다.
            } else{
                if (isDna(dnaCheck, check)) answer++;

                int idx1 = findIdx(dnaLine.charAt(front));
                if (idx1 >= 0)  check[idx1]--;
                front++;
                size--;

            }
        }

        // 나머지 dna 처리
        if (isDna(dnaCheck, check)) answer++;


        bw.write(answer + "");
        bw.flush();
        bw.close();
    }

    // DNA가 맞는지 확인
    private static boolean isDna(int[] dnaCheck, int[] check) {
        boolean flag = true;
        for (int i = 0; i < 4; i++) {
            if (dnaCheck[i] > check[i]) {
                flag = false;
                break;
            }
        }
        return flag;
    }


    // DNA로 변환
    private static int findIdx(char word) {
        if (word == 'A') return 0;
        else if (word == 'C') return 1;
        else if (word == 'G') return 2;
        else if (word == 'T') return 3;

        return -1;
    }

}

 

 

 

❗ 오답노트 / 필요한 지식

1.  투포인터 정말 어렵다. 머리아프다. ㅋㅋ 많이 풀어보는 수 밖에 없다.
2. 항상 생각, 간단한 예제를 통해 검증