슬라이딩 윈도우 알고리즘
2개의 포인터로 범위를 지정한 다음 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결한다.
[백준 12891번] DNA 비밀번호
https://www.acmicpc.net/problem/12891
P와 S의 길이가 1,000,000으로 매우 크기 때문에 O(n)의 시간 복잡도 알고리즘으로 문제를 해결해야 한다. 이때 부분 문자열의 길이가 P 이므로 슬라이딩 윈도우 개념을 이용하면 문제를 쉽게 해결할 수 있다.
그림을 보면 마치 창틀에 창문을 놓고 이동하듯이 길이가 P인 윈도우를 지정하여 배열 S의 시작점에 놓은 후 같은 길이 그대로 오른쪽으로 밀고 있다. 배열 S의 길이만큼만 탐색을 진행하면 되므로 O(n)의 시간 복잡도로 문제를 해결할 수 있다. 문제 풀이 과정은 다음과 같다.
- S 배열과 비밀번호 체크 배열을 저장한다.
- 윈도우에 포함된 문자로 현재 상태 배열을 만든다. 그런 후 현재 상태 배열과 비밀번호 체크 배열을 비교하여 유효 비밀번호인지 판단한다.
- 윈도우를 한 칸씩 이동하며 현재 상태 배열을 업데이트한다. 그 후 다시 비밀번호 체크 배열과 비교하여 유효성을 판단한다. 현재 상태 배열을 업데이트할 때는 빠지는 문자열, 신규 문자열만 보고 업데이트하는 방식으로 진행한다. (예를 들어 현재 상태 배열이 1, 2, 2, 3 이었을 때 윈도우를 한 칸 이동해 C가 빠지고, G가 추가되었다면 이 배열을 1, 1, 3, 3으로 업데이트하는 방식)
이 문제는 슬라이딩 윈도우 원리 외에도 '실제 문자열과 관련된 배열 처리를 어떻게 할 것인가?', '비밀번호 유효성 검사를 보다 빠르게 할 수 있는 방법이 있는가?' 등 코드 레벨에서 고민이 필요한 부분이 있다.
유효한 비밀번호를 검사할 때 기존 검사 결과에 새로 들어온 문자열, 제거되는 문자열만 반영하여 확인하는 것이 핵심이다.
나는 일단 각 문자의 개수 자체가 최소로 요구하는 문자 수 이상으로 있는지 우선 확인하고, 있다면 투 포인터 알고리즘처럼 i와 j의 값을 지정한 후 둘을 하나씩 증가시키며 매번 문자열을 잘라 해당 문자열의 A,C,G,T 문자 개수를 계속 구하며 비교하였다. 답은 나오는데 시간 초과가 걸렸다. 앞으론 시간을 최소화하는 방법을 우선적으로 먼저 생각해 봐야겠다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
static int[] checkArr = new int[4]; // 비밀번호 체크 배열 (필요 최소 개수)
static int[] myArr = new int[4]; // 현재 상태 배열
static int answer = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int s_len = Integer.parseInt(st.nextToken()); // DNA 문자열 길이
int p_len = Integer.parseInt(st.nextToken()); // 부분문자열 길이
char[] str = br.readLine().toCharArray(); // DNA 문자열
st = new StringTokenizer(br.readLine());
for (int i = 0; i < 4; i++) {
checkArr[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < p_len; i++) { // 첫 부분문자열 셋팅 (0~p_len-1) 까지
if (str[i]=='A') myArr[0]++;
if (str[i]=='C') myArr[1]++;
if (str[i]=='G') myArr[2]++;
if (str[i]=='T') myArr[3]++;
}
if (checkCounting())// {‘A’, ‘C’, ‘G’, ‘T’} 4개의 문자가 모두 최소개수를 만족했다면
answer++; // 만들 수 있는 비밀번호 개수 증가
/**
* 부분문자열 만들기 => 이전 부분문자열의 첫 문자는 제외하고, 끝에서 1문자를 더 추가한다.
*/
for (int j = p_len; j < s_len; j++) { // 부분문자열의 끝을 나타내는 위치
int i = j - p_len; // 이전 부분문자열의 시작을 나타내는 위치
// 이전 부분문자열의 시작 문자 제외
if (str[i]=='A') myArr[0]--;
if (str[i]=='C') myArr[1]--;
if (str[i]=='G') myArr[2]--;
if (str[i]=='T') myArr[3]--;
// 이전 부분문자열의 끝에서 1문자 추가
if (str[j]=='A') myArr[0]++;
if (str[j]=='C') myArr[1]++;
if (str[j]=='G') myArr[2]++;
if (str[j]=='T') myArr[3]++;
if (checkCounting())// {‘A’, ‘C’, ‘G’, ‘T’} 4개의 문자가 모두 최소개수를 만족했다면
answer++; // 만들 수 있는 비밀번호 개수 증가
}
System.out.println(answer);
}
public static boolean checkCounting() {
for (int i = 0; i < 4; i++) {
if (myArr[i] < checkArr[i])
return false;
}
return true;
}
}출처 : https://jyeonnyang2.tistory.com/321
[백준] 12891번: DNA 비밀번호 - java
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 s_len; static int p_len; static char[] str; static int[] checkArr = new i
jyeonnyang2.tistory.com
[원본]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int s = sc.nextInt();
int p = sc.nextInt();
String dna = sc.next();
int[] acgt = new int[4];
for (int i = 0; i < 4; i++) {
acgt[i] = sc.nextInt();
}
int[] cnt_acgt = new int[4];
String tmp_dna = dna;
cnt_acgt[0] = cntChar('A', tmp_dna);
cnt_acgt[1] = cntChar('C', tmp_dna);
cnt_acgt[2] = cntChar('G', tmp_dna);
cnt_acgt[3] = cntChar('T', tmp_dna);
if(cnt_acgt[0] < acgt[0] || cnt_acgt[1] < acgt[1] || cnt_acgt[2] < acgt[2] || cnt_acgt[3] < acgt[3]) {
System.out.println(0);
return;
}
int count = 0;
int i = 0, j = p;
while(j < s + 1) {
tmp_dna = dna.substring(i, j);
cnt_acgt[0] = cntChar('A', tmp_dna);
cnt_acgt[1] = cntChar('C', tmp_dna);
cnt_acgt[2] = cntChar('G', tmp_dna);
cnt_acgt[3] = cntChar('T', tmp_dna);
if(cnt_acgt[0] >= acgt[0] && cnt_acgt[1] >= acgt[1] && cnt_acgt[2] >= acgt[2] && cnt_acgt[3] >= acgt[3])
count++;
i++; j++;
}
System.out.println(count);
}
public static int cntChar(char c, String str) {
return str.length() - str.replaceAll(String.valueOf(c), "").length();
}
}
[백준 11003번] 최솟값 찾기
https://www.acmicpc.net/problem/11003
일정 범위 안에서 최솟값을 구하는 문제이므로 슬라이딩 윈도우와 정렬을 사용하면 될 것 같다. 윈도우의 크기는 범위가 i-L+1 ~ i 이므로 L이 된다. 최솟값을 찾기 위한 정렬은 어떨까? 일반적으로 정렬은 nlog(n)의 시간 복잡도를 가지므로 N과 L의 최대 범위가 5,000,000인 이 문제에서는 정렬을 사용할 수 없다. 즉 O(n)의 시간 복잡도로 해결해야 한다. 하지만 슬라이딩 윈도우를 덱(deque)으로 구현하여 정렬 효과를 볼 수 있다. 덱은 양 끝에서 데이터를 삽입하거나 삭제할 수 있는 자료구조이며 왼쪽에서는 addFirst(), removeFirst() 함수가 삽입, 삭제 역할을 하고 오른쪽에서는 addLast(), removeLast() 함수가 삽입, 삭제 역할을 한다.
덱에서는 (인덱스, 숫자) 형태의 노드를 클래스로 구현하여 저장한다. 새 노드를 저장할 때 덱 뒤에서부터 비교하며 만약 삽입하는 숫자가 더 작다면 기존에 있던 노드를 제거(removeLast)한다. (어차피 최소값이 필요한 것이므로 큰 값들은 필요 없음). 삽입하는 숫자가 더 크다면 탐색을 멈추고 덱에 저장(addLast)한다. 이렇게 하면 노드는 오름차순으로 정렬이 되어있는 상태가 된다. 바로 이것이 덱을 이용하여 정렬 효과를 보는 방법이다. 최솟값을 찾기 위해서는 그저 덱 처음에 있는 노드의 숫자를 출력하면 된다. 자동으로 최솟값이 맨 앞에 있게 되어있기 때문이다.
이렇게 계속해서 노드를 추가할 때 인덱스 범위가 슬라이딩 윈도우를 벗어나게 되는데, 이는 노드의 인덱스를 보면 확인할 수 있다. (1, 1), (3, 2), (4, 3)이 덱에 있다고 가정했을 때 인덱스 범위는 1 ~ 4가 되므로 윈도우 범위인 3을 벗어나게 된다. 최솟값은 윈도우 범위 내에서 찾아야 하므로 (1, 1)은 덱에서 제거(removeFirst)된다. 제거가 끝난 후 유효한 범위내의 최솟값인 2를 출력한다.
즉, 숫자 비교, 윈도우 범위 계산이 끝난 덱에서 맨 앞에 있는 노드의 숫자를 출력하기만 하면 정답이 되는 것이다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
static class Node {
public int index;
public int value;
Node(int index, int value) {
this.index = index;
this.value = value;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 출력을 버퍼에 넣고 한 번에 출력하기 위해 BufferedWriter 사용
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int L = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
Deque<Node> deque = new LinkedList<>();
for (int i = 0; i < N; i++) {
int now = Integer.parseInt(st.nextToken());
// 새로운 값이 들어올 때마다 정렬 대신 현재 수보다 큰 값을 덱에서 제거해 시간 복잡도를 줄임
while(!deque.isEmpty() && deque.getLast().value > now) {
deque.removeLast();
}
deque.addLast(new Node(i, now));
// 범위에서 벗어난 값은 덱에서 제거
if(deque.getFirst().index <= i - L)
deque.removeFirst();
bw.write(deque.getFirst().value + " ");
}
bw.flush();
bw.close();
}
}(Scanner 사용시 시간 초과)
난 앞의 문제처럼 푼답시고 배열을 생성한 후 초기값 넣고 범위 내에서 최솟값을 찾은 후 하나씩 값 대입하며 범위 내에서 최솟값 찾도록 하였다. 시간 초과가 났는데 for 루프 안에서 findMin 함수를 호출해 배열 루프 돌며 최솟값 찾는 과정이 있으니 O(n^2) 가 되어버려 당연한 듯 싶다.
[원본]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int L = sc.nextInt();
long[] A = new long[N];
for (int i = 0; i < N; i++) {
A[i] = sc.nextLong();
}
long[] D = new long[N];
for (int i = 0; i < L; i++) { // 초기 배열 설정
D[i] = A[i];
System.out.print(findMin(D, 0, i) + " ");
}
for (int j = L; j < N; j++) {
int i = j - L + 1;
D[j] = A[j];
System.out.print(findMin(D, i, j) + " ");
}
}
public static long findMin(long[] arr, int i, int j) {
long min = arr[i];
for (int k = i; k <= j; k++)
min = Math.min(min, arr[k]);
return min;
}
}
[참고자료]
Do it! 알고리즘 코딩테스트 자바편
https://jyeonnyang2.tistory.com/321
[백준] 12891번: DNA 비밀번호 - java
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 s_len; static int p_len; static char[] str; static int[] checkArr = new i
jyeonnyang2.tistory.com
'알고리즘 > Do it! 알고리즘 코딩 테스트' 카테고리의 다른 글
| 버블 정렬 (Bubble sort) (0) | 2024.05.15 |
|---|---|
| 스택과 큐 (1) | 2024.05.15 |
| 투 포인터 (0) | 2024.05.10 |
| 구간 합 (0) | 2024.05.09 |
| 배열과 리스트 (0) | 2024.05.09 |
