12891 - DNA 비밀번호 (Java)

 

---

 

문제

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

 

풀이

단순한 문제이다.

 

앞에서부터 부분문자열 만큼 range 를 잡고 그 구성에 최소한의 알파벳 개수가 있는지 체크하면 된다.

 

이후로 한칸씩 이동시키면서 알파벳 개수를 체크하면 된다.

 

투 포인터? 라고 해야할까, 앞 뒤 인덱스 각각 하나씩을 기억하고 이동시키면서 알파벳 개수 체크만 잘하면 되는 문제이다.

 

코드

import java.util.*;
import java.io.*;

public class Main {

    public void solution() throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Integer dnaLen = Integer.parseInt(st.nextToken());
        Integer partialLen = Integer.parseInt(st.nextToken());
        Integer answer = 0;
        String dnaString = br.readLine();
        st = new StringTokenizer(br.readLine());

        Integer minimumA = Integer.parseInt(st.nextToken());
        Integer minimumC = Integer.parseInt(st.nextToken());
        Integer minimumG = Integer.parseInt(st.nextToken());
        Integer minimumT = Integer.parseInt(st.nextToken());

        int currentAlphas[] = new int[100];
        
        for (int i = 0; i < partialLen; i++) {
            currentAlphas[dnaString.charAt(i)]++;
        }

        if ( currentAlphas['A'] >= minimumA && currentAlphas['C'] >= minimumC &&
             currentAlphas['G'] >= minimumG && currentAlphas['T'] >= minimumT) {
            answer++;
        }

        int frontIdx = 1;
        int backIdx = partialLen;

        while (true) {
            if (backIdx == dnaLen) break;

            currentAlphas[dnaString.charAt(frontIdx-1)]--;
            currentAlphas[dnaString.charAt(backIdx)]++;

            frontIdx++;
            backIdx++;

            if ( currentAlphas['A'] >= minimumA && currentAlphas['C'] >= minimumC &&
                 currentAlphas['G'] >= minimumG && currentAlphas['T'] >= minimumT) {
                answer++;
            }
        }

        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }


}

 

후기

 

처음엔 알파벳을 골라서 해야하는건줄 알고 헷갈렸는데, 부분 문자열이 연속된 문자열인걸 나중에 깨닫고 바로 풀었다.