슬라이딩 윈도우란??
고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 말한다. 배열이나 리스트의 요소의 일정 범위의 값을 비교할때 사용하면 매우 유용하다. 원래 네트워크에서 사용되던 알고리즘을 문제풀이에 응용한 경우라고 할 수 있다.
문제 풀이시 주로 사용되는 경우에는 배열과 그 부분배열을 어떤 조건하에서 계산하는 경우에 주로 사용된다. 예를 들어, 구간 합 구하기, 부분 문자열 구하기등에 활용될 수 있다.
슬라이딩윈도우와 투포인터
이런 슬라이딩 윈도우와 함께 자주 언급되는 알고리즘으로 투포인터 알고리즘이 있다.
투 포인터와 슬라이딩 윈도우 알고리즘은 선형 공간(1차원 배열)을 2회 이상 반복적으로 탐색해야 할 경우 O(N²) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있다는 공통점이 있다.
그렇다면 이 두 알고리즘의 차이점은 무엇일까?
바로, 부분 배열 길이의 변화 여부이다.
쉽게 말해서, 투 포인터 알고리즘은 부분 배열의 길이가 가변적이지만 슬리이딩 윈도우 알고리즘은 부분 배열의 길이가 고정적이다.
또 다른 차이점은 투 포인터 알고리즘은 부분 배열의 길이가 가변적이기 때문에 부분 배열의 구간을 정할 2개의 포인터 변수가 필요한 반면, 슬라이딩 윈도우 알고리즘은 부분 배열의 길이를 고정적으로 잡기 때문에 포인터 변수가 2개일 필요가 없다. 즉, 고정적인 부분 배열의 크기를 나타내는 변수가 있다면 포인터 하나만 있어도 부분 배열의 크기를 알고 있기 때문에 각 배열의 끝을 어딘지 알 수 있다.
투 포인터에 대해서는 다음에 알아보기로 하고 이번 글에서는 슬라이딩 윈도우에 대해서만 정리하려고 한다.
슬라이딩 윈도우 동작원리
{A, A, A, C, C, T, G, C}라는 배열이 있다고 가정해보자. 그리고 이 배열에서 길이가 3인 부분 문자열을 슬라이딩 윈도우를 이용해 구한다고 하면 어떻게 구해야할까?
먼저, 길이가 3인 부분집합의 초기배열을 설정한다.
그리고 제일 앞에 요소를 제거한 후, 제일 마지막요소의 다음요소를 부분문자열에 포함시킨다.
위에서 했던 과정을 반복하며 부분 문자열을 구한다.
생각보다 원리 자체는 간단하다 그럼 이제 슬라이딩 윈도우를 활용해 문제를 풀어보자.
슬라이딩 윈도우를 활용한 문제풀이
위 문제는, 주어진 문자열의 부분집합을 구하는 문제이다. 이 경우 주어지는 문자열의 길이가 최대 1_000_000이다. 처음에는 재귀로 부분집합을 구하는 방법을 생각했지만 시간복잡도를 생각해보니 무조건 시간초과가 될 것 같다는 생각이 들었다.
그래서 다른 방법을 고민하다가 생각난 것이 슬라이딩 윈도우였다.
배열이 4개로 고정되어 있고 부분문자열을 찾는 문제이기 때문에 시작 인덱스와 끝 인덱스를 옮기는 슬라이딩 윈도우를 적용하기 적합하다고 생각했다.
먼저, 시작되는 부분문자열은 0~P-1까지이기 때문에 첫 부분문자열을 저장하고 각 문자 하나하나에 대해 문제에서 제시한 부분문자열 조건인 {A, C, G, T}의 개수를 저장한다.
final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
final Map<Character, Integer> passwordRule = new HashMap<>();
passwordRule.put('A', Integer.parseInt(stringTokenizer.nextToken()));
passwordRule.put('C', Integer.parseInt(stringTokenizer.nextToken()));
passwordRule.put('G', Integer.parseInt(stringTokenizer.nextToken()));
passwordRule.put('T', Integer.parseInt(stringTokenizer.nextToken()));참고로, 배열을 사용하면 조건문이 너무 많아져서 코드가 복잡해질것 같아서 Map을 사용했다.
final Map<Character, Integer> newPassword = new HashMap<>();
for (int i = 0; i < p; i++) {
newPassword.put(dna[i], newPassword.getOrDefault(dna[i], 0) + 1);
}
int answer = 0;
if (checkCount(passwordRule, newPassword)) {
answer++;
}처음 설정한 부분문자열이 문제에서 제시한 부분문자열의 조건을 만족한는지 확인한다. (checkCount() -> 부분문자열 조건확인 함수)
만약, 문제에서 제시한 부분문자열의 조건을 만족하면 비밀번호의 개수인 answer를 증가시켜준다.
int point;
for (int i = p; i < s; i++) {
point = i - p;
newPassword.put(dna[i], newPassword.getOrDefault(dna[i], 0) + 1);
// 끝 인덱스를 옮겨 부분 문자열을 수정한다.
newPassword.put(dna[point], newPassword.get(dna[point]) - 1);
// 시작 인덱스를 옮겨 부분문자열을 수정한다.
if (checkCount(passwordRule, newPassword)) {
answer++; // 조건확인후 비밀번호 개수를 증가시켜준다.
}
}for 문으로 p번 인덱스부터 전체문자열의 끝-1 인덱스까지 돌면서 부분문자열의 시작 및 끝문자를 갱신한다.
그리고 새로 만들어진 부분문자열에 대해 각 문자가 조건을 만족하면 answer를 증가시켜준다.
