[Java] DAT(Direct Address Table) 알고리즘

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

 

동작방식

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

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

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

시간복잡도

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

참고사이트

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

Direct Address Table - GeeksforGeeks

기본코드

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

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              <== 결과