2개의 포인터로 범위를 지정한 후, 범위를 유지한 채로 이동하면서 해결하는 알고리즘
+투포인터 알고리즘과 비슷함
+시간복잡도: n
package baekjoon;
import java.util.Scanner;
public class Baekjoon12891 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int string_length = input.nextInt();
int part_string_length = input.nextInt();
String temp = input.nextLine(); // 엔터 먹기
String string = input.nextLine();
String[] string_arr= string.split("");//문자열을 받아서 한 알파벳씩 배열에 넣어줌
int[] arr = new int[4]; //부분문자열의 AGCT 개수를 넣을 배열
int[] AGCT_arr= new int[4];
for(int i=0; i<4; i++) {//AGCT의 최소 개수가 들어있는 배열
AGCT_arr[i] = input.nextInt();
}
int cnt=0;
for(int i=0; i<part_string_length;i++) {
if(string_arr[i].equals("A")) {
arr[0]++;
}
if(string_arr[i].equals("C")) {
arr[1]++;
}
if(string_arr[i].equals("G")) {
arr[2]++;
}
if(string_arr[i].equals("T")) {
arr[3]++;
}
}
for(int i=0;i<string_length-part_string_length+1;i++) {
if((arr[0]>=AGCT_arr[0])&&(arr[1]>=AGCT_arr[1])&&(arr[2]>=AGCT_arr[2])&&(arr[3]>=AGCT_arr[3])) {
cnt++;
}
//===================================
//기존 부분 문자열의 첫 문자의 갯수 제거
if(string_arr[i].equals("A")) {
arr[0]--;
}
if(string_arr[i].equals("C")) {
arr[1]--;
}
if(string_arr[i].equals("G")) {
arr[2]--;
}
if(string_arr[i].equals("T")) {
arr[3]--;
}
//======================================
//기존 부분 문자열에서 새로운 문자열 추가
if(string_arr[i+part_string_length].equals("A")) {
arr[0]++;
}
if(string_arr[i+part_string_length].equals("C")) {
arr[1]++;
}
if(string_arr[i+part_string_length].equals("G")) {
arr[2]++;
}
if(string_arr[i+part_string_length].equals("T")) {
arr[3]++;
}
}
}
}
사실.. 이 코드는 오류남.. ㅎ
왜지 왜 때문이지 좀 더 고민해보고 수정하겠어요