슬라이딩윈도우

지선·2023년 3월 25일

알고리즘study

목록 보기
6/7

슬라이딩 윈도우란?

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]++;
			}
			
		}
		
	}	

}

사실.. 이 코드는 오류남.. ㅎ
왜지 왜 때문이지 좀 더 고민해보고 수정하겠어요

profile
긍정왕되기

0개의 댓글