백준 12891번: DNA 비밀번호 [투 포인터][누적합][구간합] -Java

 

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

12891번: DNA 비밀번호

 

누적합 방법, 투 포인터 방법으로 각각 풀었던 것에 대해 작성한다.

 

 

<누적합 Java 코드>

누적합은 i 부터 j 번째까지의  A,C,G,T의 갯수를 모두 카운팅하고  i-1 을 빼주는 방식

쓸데없는 변수 선언이 꽤 많다.

 

투포인터인척 하는 누적합 방식...^^;;

시간 복잡도는 당연히 O(N) = O(S)

package algorithm.boj;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj12891 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int S = Integer.parseInt(st.nextToken());
		int P = Integer.parseInt(st.nextToken());

		// 1부터 시작
		char arr[] = new char[S + 1];
		int Acnt[] = new int[S + 1];
		int Ccnt[] = new int[S + 1];
		int Gcnt[] = new int[S + 1];
		int Tcnt[] = new int[S + 1];

		st = new StringTokenizer(br.readLine());
		String str = st.nextToken();

		//DNA 문자 누적합
		for (int i = 1; i <= S; i++) {
			arr[i] = str.charAt(i-1);
			switch (arr[i]) {
			case 'A': {
				Acnt[i] = Acnt[i - 1] + 1;
				Ccnt[i] = Ccnt[i - 1];
				Gcnt[i] = Gcnt[i - 1];
				Tcnt[i] = Tcnt[i - 1];
				break;
			}
			case 'C': {
				Acnt[i] = Acnt[i - 1];
				Ccnt[i] = Ccnt[i - 1] + 1;
				Gcnt[i] = Gcnt[i - 1];
				Tcnt[i] = Tcnt[i - 1];
				break;
			}
			case 'G': {
				Acnt[i] = Acnt[i - 1];
				Ccnt[i] = Ccnt[i - 1];
				Gcnt[i] = Gcnt[i - 1] + 1;
				Tcnt[i] = Tcnt[i - 1];
				break;
			}
			case 'T': {
				Acnt[i] = Acnt[i - 1];
				Ccnt[i] = Ccnt[i - 1];
				Gcnt[i] = Gcnt[i - 1];
				Tcnt[i] = Tcnt[i - 1] + 1;
				break;
			}
			}
		}
		
		//필수 조건 저장
		int valid[] = new int[4]; //A C G T 순서
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < 4; i++) {
			valid[i] = Integer.parseInt(st.nextToken());
		}
		
		//체크
		// 투 포인터 생성
		int idx1 = 1;
		int idx2 = P;
		
		int res = 0;
		
		//범위 탐색
		while (idx1 <= S && idx2 <= S) {
			//범위까지의 A,C,G,T 갯수 파악하기
			int a = Acnt[idx2]-Acnt[idx1-1];
			int c = Ccnt[idx2]-Ccnt[idx1-1];
			int g = Gcnt[idx2]-Gcnt[idx1-1];
			int t = Tcnt[idx2]-Tcnt[idx1-1];
			
			if( a >= valid[0]
				&& c >= valid[1]
				&& g >= valid[2]
				&& t >= valid[3] ) {
				res++;
			}
			
			idx1++;
			idx2++;
		}
		
		System.out.println(res);
	}

}

 

 

<투 포인터 Java 코드>

투 포인터 방식으로 풀기.

 

Ex. 문자열은 AAACCTGCCAA / 부분문자열은 4라고 가정한다.

AAAC

  AACC

    ACCT

      CCTG

         CTGC

            TGCC

....

이런식으로 한칸씩 옮기면서 A,C,G,T의 최소 만족갯수를 파악해야하는데,

이때 늘 부분 문자열만큼 다 계산하지말고 앞전에 썼던 문자열의 A,C,G,T 갯수를 이용한다.

 

AAAC

  AACC

....

이렇게 AAC가 중복이니 앞전 문자열에서 가장 시작점인 idx의 알파벳 A만 카운팅에서 빼준다. 그리고 뒤의 C를 다시 카운팅한다.

 

얘도 시간복잡도는 O(N) = O(S) !

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int S = Integer.parseInt(st.nextToken());
		int P = Integer.parseInt(st.nextToken());
		
		char arr[] = new char[S];
		st = new StringTokenizer(br.readLine());
		
		String str = st.nextToken();
		for (int i = 0; i < S; i++) {
			char ch = str.charAt(i);
			arr[i] = ch;
		}
		
		int valid[] = new int[4];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < 4; i++) {
			valid[i] = Integer.parseInt(st.nextToken());
		}
		
		
		int cnt[] = new int[4]; //현재의 ACGT별 갯수
		
		int res = 0;
		//투 포인터 탐색 전 최초 0 ~ P 까지의 갯수 구성 파악
		for (int i = 0; i < P; i++) {
			cnt[charToIndex(arr[i])]++;
		}
		
		//idx 0 ~ P 까지는 최소 개수 조건에 만족하는가?
		if(chkValid(valid,cnt))
			res++;
		
		
		//이제부터 이전 문자열을 참고하여 투포인터 시작
		for (int i = 1; i <= S-P; i++) {
			//맨 앞의 알파벳은 범위미포함이니 카운팅에서 제거
			cnt[charToIndex(arr[i-1])]--;
			//가장 마지막 알파벳은 카운팅이 안되어있으니 카운트
			cnt[charToIndex(arr[i+P-1])]++;
			
			//최소 개수 조건에 만족하는지 체크
			if(chkValid(valid,cnt))
				res++;
		}

		System.out.println(res);
	}
	
	public static int charToIndex(char ch) {
		if(ch == 'A')
			return 0;
		else if(ch == 'C')
			return 1;
		else if(ch == 'G')
			return 2;
		else
			return 3;
	}
	
	public static boolean chkValid(int[] valid, int[] cnt) {
		
		for (int i = 0; i < 4; i++) {
			if(valid[i] > cnt[i]) //최소조건보다 현재가 적으면 바로 탈락
				return false;
		}
		return true;
		
	}

}