[백준/Java] #12891 DNA 비밀번호

📝 DNA 비밀번호

사용 언어 : Java
레벨 : 실버 2

 

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

 

🔎 문제 설명

 

✅ 풀이

투 포인터와 비슷하게 풀면 되는 문제였다. 나는 HashMap 을 이용해서 inputCnt 에는 필요한 문자의 개수들을 넣어줬고, pwCnt 에는 부분 문자열에서 각 문자의 개수를 넣어줘서 풀었다! 처음에 들어올 때 A, C, G, T의 필요한 문자의 개수가 0이라면 cnt (필요한 문자의 개수와 부분 문자열의 문자 개수가 같은 개수를 카운팅하는 변수) 를 늘려주었다.

일단 add() 메서드와 remove() 메서드를 작성했는데, add에서는 내 문자 map인 pwCnt 에서 입력받은 문자의 카운팅을 하나 늘려주고, 만약 하나 늘린 값이 inputCnt map 에 필요한 개수와 일치한다면 cnt를 하나 증가시켜주었다.

remove 에서는 지금 값이 필요한 개수와 일치한다면 먼저 cnt를 하나 감소시킨 뒤, pwCnt 에서 입력받은 문자의 카운팅을 하나 빼주는 식으로 작성했다.

우선 0 ~ p - 1 까지의 부분 문자열을 add 메소드에 넣어서 초기 문자열을 세팅해주고 이 시점에서 cnt 가 4라면 (모두 필요한 문자의 개수만큼 있다면) result 에 1을 증가시켜서 기본 값으로 세팅해놓고 while 문을 돌려서 본격적인 투 포인터 형식으로 풀었다.

주의할 점은 startIdx는 증가시키 전에 메소드를 실행해야 해서 초기값을 0으로 두었고, endIdx 는 증가시킨 뒤에 메소드를 실행해야 해서 초기값을 p로 두었다. 그리고 endIdx < s 일 때까지 반복하면서 add(pw[endIdx]), remove(pw[startIdx]) 를 실행시키고, 이 시점에서 cnt가 4라면 result 에 하나씩 추가해주는 방식으로 풀어봤다!

포인트를 이동시킬 때 어떤 포인트는 이동하기 전 메소드 실행, 어떤 포인트는 메소드 실행 후 이동해야된다는 점이 생각보다 많이 헷갈렸던 것 같다. 🥲

 

💻 최종 코드

import java.io.*;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    static HashMap<String, Integer> pwCnt = new HashMap<>();
    static HashMap<String, Integer> inputCnt = new HashMap<>();
    static int cnt = 0;

    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[] pw = br.readLine().split("");

        st = new StringTokenizer(br.readLine());
        inputCnt.put("A", Integer.parseInt(st.nextToken()));
        inputCnt.put("C", Integer.parseInt(st.nextToken()));
        inputCnt.put("G", Integer.parseInt(st.nextToken()));
        inputCnt.put("T", Integer.parseInt(st.nextToken()));

        for (String key : inputCnt.keySet()) {
            pwCnt.put(key, 0);
            if (inputCnt.get(key) == 0) {
                cnt++;
            }
        }

        int result = 0;

        // 초기 문자열 설정
        for (int i = 0; i < p; i++) {
            add(pw[i]);
        }

        // 초기 문자열 확인
        if (cnt == 4) {
            result++;
        }

        int startIdx = 0;
        int endIdx = p;

        while (endIdx < s) {
            add(pw[endIdx]);
            remove(pw[startIdx]);
            if (cnt == 4) {
                result++;
            }

            endIdx++;
            startIdx++;
        }


        bw.write(String.valueOf(result));
        bw.close();
    }

    public static void add(String s) {
        pwCnt.put(s, pwCnt.get(s) + 1);
        if (pwCnt.get(s).equals(inputCnt.get(s))) {
            cnt++;
        }
    }

    public static void remove(String s) {
        if (pwCnt.get(s).equals(inputCnt.get(s))) {
            cnt--;
        }
        pwCnt.put(s, pwCnt.get(s) - 1);
    }
}