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구간에서 가장 많이 나오는 알파벳을 알아낼 수 있습니다.

DAT는 자료구조입니다. 값을 배열의 index를 활용하는 것이 포인트 입니다. 

동작방식

배열을 사용하여 레코드를 해당 키에 매핑할 수 있는 데이터 구조입니다. 직접 주소 테이블에서 레코드는 키 값을 인덱스로 직접 사용하여 배치됩니다. 빠른 검색, 삽입 및 삭제 작업을 용이하게 합니다.

최대값에 1을 더한 크기의 배열을 만든 다음(0 기반 인덱스로 가정) 값을 인덱스로 사용합니다. 예를 들어 다음 다이어그램에서 키 21은 인덱스로 직접 사용됩니다.

시간복잡도

탐색,삽입,삭제 연산을 모두 O(1)

참고사이트

https://www.geeksforgeeks.org/direct-address-table/

기본코드

아래는 글을 입력받아 가장 많이 나온 문자를 찾아내는 간단한 코드입니다.

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


public class DAT_example {
	
	/**
	 * DTA : Direct Address Table 자료구조 
	 * ==> 값을 index로 활용하는 것인 포인트
	 */
	
	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 input = br.readLine();
		int[] arr = new int[200];
		int max = 0;
		String maxChar = "";
		for(int i=0; i<input.length(); i++){
			arr[input.charAt(i)] += 1;
			if(arr[input.charAt(i)]  > max){
				max = arr[input.charAt(i)] ;
				maxChar = input.charAt(i)+"";
			}
		}
		
		// 풀이
		System.out.println(maxChar);
		
		br.close();
		bw.close();
	}

}

결과

AMDKIDD   <== 입력
D              <== 결과