Typiler

이번에는 슬라이딩 윈도우 알고리즘과 DAT 자료구조를 이용한 간단한 문제를 풀어보겠습니다.

문제

입력된 문자열(알파벳)에서 길이가 M개의 구간에서 가장 많이 등장하는 알파벳을 출력하라

문자열 : "AAAABBBBAABKKKABKKKKDKAAA"
M: 6

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;


public class SlidingWindow_DAT {

	
	/**
	 * 슬라이등 윈도우 + DAT
	 */
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    public static void main(String[] args) throws IOException {        

        String str = "AAAABBBBAABKKKABKKKKDKAAA";
        int n = str.length();
        int m = 6;

        int[] dat = new int[100];

        //초기세팅 6개 DAT
        char maxCh = ' ';
        int maxCnt = 0;

        for (int i = 0; i<m; i++) {
            dat[str.charAt(i)]++;
            if (dat[str.charAt(i)] > maxCnt) {
                maxCnt = dat[str.charAt(i)];
                maxCh = str.charAt(i);
            }
        }

        //슬라이딩 윈도우
        for (int i = 0; i<n - m; i++) {            
            //다음 준비
            dat[str.charAt(i + m)]++;            
            dat[str.charAt(i)]--;    

            if (dat[str.charAt(i + m)] > maxCnt) {
                maxCnt = dat[str.charAt(i + m)];
                maxCh = str.charAt(i + m);
            }
        }

        System.out.println(maxCh);

        bw.close();
        br.close();
    }    

}

풀이

dat 배열에 길이가 M인 구간에서 나타나는 알파벳을 카운트하여 줍니다. 문자열 AAAABBBBAABKKKABKKKKDKAAA에서 처음 AAAABB 를 확인하면 dat 배열 dat['A']는 4, dat['B'] 는 2가 들어갑니다. 그리고 다음으로 이동합니다. 슬라이딩 윈도우 알고리즘으로 길이가 6인 구간을 기준으로 뒤문자는 카운트를 더해주고, 앞문자는 카운트에서 빼줍니다. 작업이 완려되면 dat배열에 문자번째와 max변수를 비교하여 max변수를 갱신합니다. 이러한 방식으로 M구간에서 가장 많이 나오는 알파벳을 알아낼 수 있습니다.

슬라이딩 윈도우 알고리즘은 배열 요소의 일정 범위 값을 비교할때 사용하면 유용한 알고리즘 입니다.

동작방식

일정 정수로 이루어진 배열 int[] arr= {3,1,5,3,4,1,5,7,5,1,8} 가 있다면, 길이가 5인 배열의 합계가 가장 큰 것은 무엇인가? 라는 문제에 사용될 수 있습니다. 일반적으로 아래와 같이 0번째 부터 4번째 (길이가 5이므로) 합을 구하고 저장합니다. 그리고 1번째 부터 5번째까지의 합을 구하고 저장후 처음에 구했던 값과 비교를 하여 큰것을 가지고 있습니다. 이렇게 반복을 하면 됩니다. 하지만 이 방법은 매번 for 루프로 모든 배열의 요소를 지정된 길이만큼 순회하며 합계를 구해 최대값을 구해야하므로 비효율적 입니다.

[3,1,5,3,4],1,5,7,5,1,8 ==> 합: 16, 최대값: 16
3,[1,5,3,4,1],5,7,5,1,8 ==> 합: 14, 최대값: 16
3,1,[5,3,4,1,5],7,5,1,8 ==> 합: 18, 최대값: 18 
...
==> 비효율적

이것을 간단히 생각해보면 처음에 해당 길이만큼 합계를 구하는 것은 어쩔수 없습니다. 하지만, 그 이후부터 매번 돌지 않고 인덱스 1~5까지의 합은 처음에 길했던 0~4까지의 합계에 0번째 배열의 값을 빼고, 5번째 배열의 값을 더한 값과 같습니다. 바로 이 부분에서 처음 구했던 0~4까지의 합계를 재사용하며 다음값을 구할 수 있는데, 이것이 슬라이딩 윈도우 알고리즘의 핵심입니다.

참고사이트

https://blog.fakecoding.com/archives/algorithm-slidingwindow/

기본코드

위 설명의 예제를 구현한 코드입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class SlidingWindow_example {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));    

    static int[] arr= {3,1,5,3,4,1,5,7,5,1,8};
    static int n;

    static int getFive(int index)
    {
        int sum= 0;
        for (int i = 0; i<5; i++) {
            sum += arr[i + index];
        }
        return sum;
    }

    public static void main(String[] args) throws IOException {        

        n = arr.length;
        int max = -9999;

        int sum = getFive(0);

        for (int i = 0; i <= n - 5; i++) {
            if (sum > max) max = sum;

            // 마지막순간에는 다음 것을 준비할 필요 없음
            if (i == n - 5) break;

            // 다음 것을 준비
            sum += arr[i + 5];
            sum -= arr[i];
        }

        System.out.println(max);

        bw.close();
        br.close();
    }        
}

결과는 26이 나옵니다.