Notice
Recent Posts
Link
- Today
- Total
hye-log
[백준]12891번 DNA 비밀번호(JAVA) + 슬라이딩 윈도우 GIF 본문
0. 문제 링크
https://www.acmicpc.net/problem/12891
12891번: DNA 비밀번호
평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”
www.acmicpc.net
1. 문제 설명
1) 임의로 만든 DNA 문자열 S를 P만큼 잘랐을 때, A, C, G, T의 최소 개수를 만족하는 비밀번호 종류의 수 구하기
2. 입출력
// input
4 2
GATA
1 0 0 1
// output
2
3. 코드
import java.io.*;
import java.util.*;
public class b12891 {
static int S, P;
static char[] strS,strP;
static int[] contains;
static char[] c = {'A', 'C', 'G', 'T'};
static int ans;
static int[] temp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
// 1. 입력
st = new StringTokenizer(br.readLine());
S = Integer.parseInt(st.nextToken()); // 임의로 만든 DNA 문자열 길이
P = Integer.parseInt(st.nextToken()); // 비밀번호로 사용할 부분문자열의 길이
strS = br.readLine().toCharArray(); // 임의로 만든 DNA 문장
strP = new char[P]; // 비밀번호로 사용할 문자열
contains = new int[4]; // A, C, G, T 최소 개수
st = new StringTokenizer(br.readLine());
for(int i = 0; i < contains.length; i++) {
contains[i] = Integer.parseInt(st.nextToken());
}
ans = 0; // 만들 수 있는 비밀번호의 종류의 수
// 2. 초기값 설정
temp = new int[4]; // 생성한 문자열의 A, C, G, T 개수
boolean flag = true;
for(int j = 0; j < P; j++) { // 생성한 문자열의 A, C, G, T 개수 세기
cntUp(strS[j]);
}
for(int j = 0; j < 4; j++) { // 필수 문자의 개수 > 생성 문자의 개수
if(contains[j] > temp[j]) {
flag = false;
}
}
if(flag == true) { // 조건을 만족하면 ans 증가
ans++;
}
// 3. S-P만큼 반복
for(int i = 1; i <= S-P; i++) {
flag = true;
cntDown(strS[i-1]); // i번째 감소
cntUp(strS[i+P-1]); // i+P번째 증가
for(int j = 0; j < 4; j++) { // 필수 문자의 개수 > 생성 문자의 개수
if(contains[j] > temp[j]) {
flag = false;
}
}
if(flag == true) { // 조건을 만족하면 ans 증가
ans++;
}
}
// 4. 출력
System.out.println(ans);
}
private static void cntUp(char c) { // 해당하는 문자의 개수 더하기
switch(c){
case 'A':
temp[0]++;
break;
case 'C':
temp[1]++;
break;
case 'G':
temp[2]++;
break;
case 'T':
temp[3]++;
break;
default:
break;
}
}
private static void cntDown(char c) { // 해당하는 문자의 개수 빼기
switch(c){
case 'A':
temp[0]--;
break;
case 'C':
temp[1]--;
break;
case 'G':
temp[2]--;
break;
case 'T':
temp[3]--;
break;
default:
break;
}
}
}
실행 결과
4. 회고
1) 슬라이딩 윈도우를 사용하여 시간 초과 해결
- 슬라이딩 윈도우 개념은 아래 gif 참고!
5. Github
https://github.com/iihye/Algorithm/blob/main/Baekjoon/b12891.java
728x90
'CodingTest > Baekjoon' 카테고리의 다른 글
[백준]2164번 카드2(JAVA) (0) | 2023.08.07 |
---|---|
[백준]2023번 신기한 소수(JAVA) (0) | 2023.08.06 |
[백준]2961번 도영이가 만든 맛있는 음식(JAVA) (0) | 2023.08.06 |
[백준]1244번 스위치 켜고 끄기(JAVA) (0) | 2023.08.06 |
[백준]11660번 구간 합 구하기 5(JAVA) (0) | 2023.08.06 |
Comments