[12891번] DNA 비번 ( 시간초과 어디서?? )

---

---

🆖 재도전 시간 초과

아래 코드와 같은 방식으로 회전 초밥 문제에서 메모리 초과를 해결했었는데, 이제 시간초과를 해결해야한다.

while문이 s-p+1 = k번 반복되고 리스트안에서 비교할 때 p=n번 반복되니까 총 시간복잡도는 O(NK)이다.
최악일 때가 s= 1,000,000, p =1 일 때니까 k=1,000,000이다.
따라서 O(N*N = 1,000,000 X 1) 이니까 while문은 ㄱㅊ다!!

어디서 시간 초과 발생한거지

??

일단 이렇게 풀면 틀리니까 슬라이딩 윈도우를 이용해서 좀 더 간략하게 풀 수 있는 방법을 강구해보자.

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

public class Main {

	static int check[];

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		int s = Integer.parseInt(st.nextToken());
		int p = Integer.parseInt(st.nextToken());

		char original[] = br.readLine().toCharArray();
		check = new int[4];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < 4; i++) {
			int alpa = Integer.parseInt(st.nextToken());
			check[i] = alpa;
		}

		int cnt = 0;

		int start = 0;
		int end = 0;

		while (end < original.length) {
			ArrayList<String> list = new ArrayList<>();
			int isContain[] = new int[4];
			end = start + p;
			for (int i = start; i < end; i++) {
				list.add(String.valueOf(original[i]));
			}

			for (String one : list) {
				if (one.equals("A")) {
					isContain[0]++;
				} else if (one.equals("C")) {
					isContain[1]++;
				} else if (one.equals("G")) {
					isContain[2]++;
				} else if (one.equals("T")) {
					isContain[3]++;
				}
			}

			if (isContain[0] == check[0] && isContain[1] == check[1] && isContain[2] == check[2] && isContain[3] == check[3]) {
				cnt++;
			}

			start++;
		}

		System.out.println(cnt);


	}

}

---

✅ 슬라이딩 윈도우 업그레이드

슬라이딩 할 때 현재 상태 배열에서 빠지는 문자만 업그레이드 시켜주면 굳이 문자열을 부분 문자열로 나누는 과정이 없어도 된다!!

---

🆙 코드

아래 코드는 for문 하나만 사용하므로 시간 복잡도는 O(n) 이다.

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

public class Main {
	static char original[];
	static int check[];
	static int current[];
	static int cnt = 0;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		int s = Integer.parseInt(st.nextToken());
		int p = Integer.parseInt(st.nextToken());

		original = br.readLine().toCharArray();
		check = new int[4];
		current = new int[4];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < 4; i++) {
			check[i] = Integer.parseInt(st.nextToken());
			if (check[i] == 0) //0이면 문자열이 없는 상태를 만족하므로 ++
				cnt++;
		}

		//초기 부분 문자열 지정
		for (int i = 0; i < p; i++) {
			addCurrent(original[i]);
		}

		int result = 0;
		//검사 여기서 한 번
		if (cnt == 4) {
			result++;
		}

		//나머지 문자열 슬라이딩 (핵심!)
		for (int i = p; i < s; i++) {
			int left = i - p;
			addCurrent(original[i]); //0,1,2
			removeCurrent(original[left]); //9,10,11
			
			//for문 안에서 확인
			if (cnt == 4) {
				result++;
			}
		}

		//검사 여기서 두 번
		System.out.println(result);
		
		br.close();
	}

	private static void addCurrent(char c) {
		switch (c) {
			case 'A':
				current[0]++;
				if (current[0] == check[0]) {
					cnt++;
				}
				break;
			case 'C':
				current[1]++;
				if (current[1] == check[1]) {
					cnt++;
				}
				break;
			case 'G':
				current[2]++;
				if (current[2] == check[2]) {
					cnt++;
				}
				break;
			case 'T':
				current[3]++;
				if (current[3] == check[3]) {
					cnt++;
				}
				break;
		}
	}

	private static void removeCurrent(char c) {
		switch (c) {
			case 'A':
				if (current[0] == check[0]) { //먼저 확인하고 --
					cnt--;
				}
				current[0]--; //그 다음 현재 상태 배열 --
				break;
			case 'C':
				if (current[1] == check[1]) {
					cnt--;
				}
				current[1]--;
				break;
			case 'G':
				if (current[2] == check[2]) {
					cnt--;
				}
				current[2]--;
				break;
			case 'T':
				if (current[3] == check[3]) {
					cnt--;
				}
				current[3]--;
				break;
		}
	}


}

---