[백준] 12891번 DNA 비밀번호 - 슬라이딩 윈도우 / switch / 함수

문제

 

 

 

로직

입력 받을 문자열의 길이 입력 받기 

부분 문자열의 길이 입력 받기

 

입력 받을 문자열을 담는 배열 선언 & 크기 설정(S로)

부분문자열에 포함되어야 할 {‘A’, ‘C’, ‘G’, ‘T’} 의 최소 개수를 담는 배열 선언 & 크기 설정

최소 개수를 입력한 문자열과 비교할 배열 선언 & 크기 설정

만들 수 있는 비밀번호 종류의 수를 담는 변수 선언 및 초기화

 

1. 반복문- 문자열 입력 받고 배열에 저장

 

2. 반복문- 최소 개수 입력 받고 배열에 저장

 

슬라이딩 윈도우를 실행할 수 있는 코드 작성

.

.

.

슬라이딩 윈도우를 하기 위해 부분 문자열마다 시작과 끝만 고치고 싶은데 그 부분이 어려웠다.

시간복잡도를 O(n)이 되도록 하려면 이중 반복문을 못 써서 이 부분에 고민이 많았다.

선형으로 반복하고 싶은데(ex - O(2n)) 그걸 어떻게 할 지 고민하던 중

참고 강의를 보며 공부하니 함수를 이용하면 된다는 걸 깨달았다.

 

 

My Code

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

public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int S = Integer.parseInt(bufferedReader.readLine());
int P = Integer.parseInt(bufferedReader.readLine());
String[] strArray = new String[S];
int[] numArray = new int[4];
int[] testNumArray = new int[4];
int count = 0;

for (int a = 0; a < S; a++){
strArray[a] = bufferedReader.readLine();
}

StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
for (int b = 0; b < 4; b++){
numArray[b] = Integer.parseInt(stringTokenizer.nextToken());
}

int start_index = 0;
int end_index = S-1;
int partstart_index = 0;
int partend_index = P-1;
switch (strArray[partstart_index]){
case "A":
testNumArray[0] += 1;
partstart_index++;
break;
case "C":
testNumArray[1] += 1;
partstart_index++;
break;
case "G":
testNumArray[2] += 1;
partstart_index++;
break;
case "T":
testNumArray[3] += 1;
partstart_index++;
break;
}
if (partstart_index == partend_index){
start_index++;
partend_index++;
}
for (int c = 0; c < 4; c++){
if (testNumArray[c] >= numArray[c])
count++;
}


}
}

 

 

문제의 핵심 & 알게된 점

변수의 범위와 시간제한으로 인해 이중 반복문을 사용하면 안되고 시간복잡도가 O(n)이 나오게 해야한다.

그 방법은 함수를 만들어 반복시키는 방법이 있었다.

그래서 Add(), Remove()라는 함수를 만들어 시작부분을 앞으로 옮기면서 뒤를 없애고

끝부분을 앞으로 옮기면서 앞을 더하는 방식인 "슬라이딩 윈도우"를 실현할 수 있었다.

int j = i - p;로 두어 j는 시작 부분, i는 끝 부분으로 설정할 수 있었다.

 

여기서 슬라이딩 윈도우란?

2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하며 문제를 해결한다.

슬라이딩 윈도우의 방식

문제 해결 논리

이렇게 슬라이딩 윈도우에 대해 이해할 수 있게 됐다.

 

또한 switch문의 if문에서 checkArray[0] == numArray[0]의 조건이 꼭 ==여야하는 이유는

같을 때로 정의해야 반복이 되지 않고 정확히 할 수 있기 때문이다.

 

이번 문제는 My Code는 실행도 제대로 안됐다.

슬라이딩 윈도우에 대해 무지했기에 어렵게 느꼈고 참고 Code를 보는게 좋을  것이다.

 

 

참고 Code

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

public class Main {
static int[] checkArray;
static int checkNum;
static int[] numArray;
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

int S = Integer.parseInt(stringTokenizer.nextToken());
int P = Integer.parseInt(stringTokenizer.nextToken());
char[] strArray = new char[S];
numArray = new int[4];
checkArray = new int[4];
checkNum = 0;
int result = 0;

strArray = bufferedReader.readLine().toCharArray();

stringTokenizer = new StringTokenizer(bufferedReader.readLine());
for (int i = 0; i<4; i++){
numArray[i] = Integer.parseInt(stringTokenizer.nextToken());
if (numArray[i]==0)checkNum++;
}

for (int i = 0; i<P; i++){
Add(strArray[i]);
}

if (checkNum == 4) result++;

for (int i = P; i<S; i++){
int j = i-P;
Add(strArray[i]);
Remove(strArray[j]);
if (checkNum == 4) result++;
}

System.out.println(result);
bufferedReader.close();
}

private static void Remove(char c) {
switch (c){
case 'A':
if (checkArray[0] == numArray[0]) checkNum--;
checkArray[0]--;
break;
case 'C':
if (checkArray[1] == numArray[1]) checkNum--;
checkArray[1]--;
break;
case 'G':
if (checkArray[2] == numArray[2]) checkNum--;
checkArray[2]--;
break;
case 'T':
if (checkArray[3] == numArray[3]) checkNum--;
checkArray[3]--;
break;
}
}

private static void Add(char c) {
switch (c){
case 'A':
checkArray[0]++;
if (checkArray[0] == numArray[0]) checkNum++;
break;
case 'C':
checkArray[1]++;
if (checkArray[1] == numArray[1]) checkNum++;
break;
case 'G':
checkArray[2]++;
if (checkArray[2] == numArray[2]) checkNum++;
break;
case 'T':
checkArray[3]++;
if (checkArray[3] == numArray[3]) checkNum++;
break;
}
}
}

 

 

참고_인프런의 Do it! 알고리즘 코딩 테스트 with JAVA