[백준 / Java] 12891번: DNA 비밀번호 (실버2)

문제 풀이 날짜: 2023.08.03
포스트 작성일: 2023.08.03

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 12891번: DNA 비밀번호 (실버2)

 

키워드

문자열, 슬라이딩 윈도우

 

풀이 접근법

• 연속된 부분 문자열을 찾아야 하기 때문에 부분 집합이나 백트랙킹을 풀 수 없다.
• 또, 입력의 크기가 1,000,000이므로 투 포인터로 모든 구간을 구하려고 하면 시간초과가 난다.
• 따라서 투 포인터의 일종이면서도 left와 right의 간격이 항상 일정한 슬라이딩 윈도우 기법으로 답을 구한다.
• 구간을 한 칸씩 옮기면서, left가 가리키는 문자는 결과에서 제하고, right가 가리키는 문자를 결과에 추가하면서 탐색한다.
• 각 부분 문자열이 포함하는 문자의 수가 문제에서 제시한 문자의 수보다 크거나 같다면 조건을 충족한다. 결과의 수를 1 증가시킨다.

 

코드

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

public class Main {

	private static int count = 0;
	
	private static Map<Character, Integer> map = new HashMap<>();

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] temp = br.readLine().split(" ");
		
		map.put('A', 0);
		map.put('C', 1);
		map.put('G', 2);
		map.put('T', 3);
		
		int S = Integer.parseInt(temp[0]);
		int P = Integer.parseInt(temp[1]);

		int[] answer = new int[4];
		int[] result = new int[4];

		String word = br.readLine();
		
		temp = br.readLine().split(" ");
		for(int i = 0; i < 4; i++) {
			answer[i] = Integer.parseInt(temp[i]);
		}
		
		for(int i = 0; i < P; i++) { //첫 구간 초기화
			char curr = word.charAt(i);
			result[map.get(curr)]++;
		}
		
		if(isSameArr(result, answer)) {
			count++;
		}

		int left = -1;
		char prev = ' ';
		char curr = ' ';
		for(int right = P; right < S; right++) { //현재 부분문자열의 끝을 가리킴
			left = right - P; //이전 부분문자열의 시작점
			
			curr = word.charAt(right);
			prev = word.charAt(left);
			result[map.get(prev)]--;
			result[map.get(curr)]++;
			
			if(isSameArr(result, answer)) {
				count++;
			}
		}

		System.out.println(count);
	}

	private static boolean isSameArr(int[] result, int[] answer) {
		for(int i = 0; i < result.length; i++) {
			if(result[i] < answer[i]) {
				return false;
			}
		}
		return true;
	}

}

 

---

슬라이딩 윈도우를 처음 사용해본 문제이다. 말만 들어서는 어려울 것 같지만 투 포인터의 응용 버전에 불과하다. 문자열 탐색에 응용하면 좋을 듯하니 잘 기억해두는 것이 좋겠다.

 

참고한 링크

https://7357.tistory.com/240

 

git 링크

(git 링크 첨부)