[Java] 슬라이딩 윈도우 + DAT

이번에는 슬라이딩 윈도우 알고리즘과 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구간에서 가장 많이 나오는 알파벳을 알아낼 수 있습니다.