[Data Structures] Direct Address Table

배열의 인덱스(Index) 값에 의미를 부여해서 사용하는 자료구조다. 저장하려는 데이터의 키(key) 값과 배열의 인덱스 값을 직접 연동시켜 데이터의 저장 위치가 키 값에 의해 결정되고, 데이터를 저장하거나 빠르게 접근하고자 할 때 사용한다.

---

Direct Address Table의 장점

배열은 인덱스에 저장된 요소의 값을 꺼내 오는데 필요한 연산의 시간 복잡도가 O(1)이다. DAT 자료 구조를 사용해 값을 저장할 경우 배열의 빠른 연산 속도를 활용해 알고리즘 문제 해결에 적용할 수 있다.

 

입력 받은 알파벳이 샘플 데이터에 존재하는지 체크하는 예제 코드

• 변수 값 초기화

// 샘플 데이터
char[][] sampleArr = { 
    {'C', 'D', 'A'}, 
    {'B', 'M', 'Z'}, 
    {'Q', 'P', 'O'} 
};

// Direct Address Table로 활용할 배열
int[] DAT = new int[128];

// 입력된 데이터
char[] input = { 'A', 'C', 'E', 'G' };

• 배열 내부 요소를 하나씩 꺼내 DAT 배열 인덱스에 기록

int row = sampleArr.length;		// alphabetArr 배열의 row 크기
int col = sampleArr[0].length;	// alphabetArr 배열의 column 크기
for (int i=0; i<row; i++) {
    for (int j=0; j<col; j++) {
        DAT[sampleArr[i][j]]++;	// alphabetArr 요소를 하나씩 가져와 DAT 인덱스에 기록
    }
}

• 입력받은 데이터가 sampleArr 배열에 존재하면 출력

for (int i=0; i<input.length; i++) {			// 입력받은 데이터의 개수만큼 반복
    int tmp = DAT[input[i]];					// check[i]에서 꺼내온 알파벳을 DAT 배열의 인덱스로 활용해 값을 tmp에 저장
    if (tmp > 0) System.out.println(input[i]);	// 해당 인덱스에서 꺼내온 값이 0보다 크면 alphabetArr에 값이 존재하는 것으로 화면에 출력
}

전체 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {

        char[] input = { 'A', 'C', 'E', 'G' };
        char[][] sampleArr = { 
            {'C', 'D', 'A'}, 
            {'B', 'M', 'Z'}, 
            {'Q', 'P', 'O'} 
        };
        int[] DAT = new int[128];

        int row = sampleArr.length;
        int col = sampleArr[0].length;
        for (int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                DAT[sampleArr[i][j]]++;
            }
        }
        
        for (int i=0; i<input.length; i++) {
            int tmp = DAT[input[i]];
            if (tmp > 0) System.out.println(input[i]);
        }

    }
}

 

샘플 데이터의 요소 별로 개수 카운팅하는 예제 코드

• 변수 값 초기화

// 샘플 데이터
char[] sampleArr = {'A', 'D', 'C', 'F', 'A', 'C', 'E', 'A'};

// Direct Address Table로 활용할 배열
int[] DAT = new int[128];

• 배열 요소를 하나씩 꺼내서 DAT 배열 인덱스에 카운팅 값 추가

for (int i=0; i<sampleArr.length; i++) {
    DAT[sampleArr[i]]++;
}

• 샘플 데이터의 알파벳 별로 카운팅 기록된 값 출력

for (char i='A'; i<'Z'; i++) {
    if (DAT[i] > 0) System.out.println(i + ": " + DAT[i]);
}

전체 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {

        char[] sampleArr = {'A', 'D', 'C', 'F', 'A', 'C', 'E', 'A'};
        int[] DAT = new int[128];

        for (int i=0; i<sampleArr.length; i++) {
            DAT[sampleArr[i]]++;
        }
        
        for (char i='A'; i<'Z'; i++) {
            if (DAT[i] > 0) System.out.println(i + ": " + DAT[i]);
        }

    }
}

 

2차원 배열 데이터를 입력 받아 숫자의 개수를 카운팅하는 예제 코드

2차원 배열을 사용하는 경우 1,000 × 1,000 행렬에 담긴 값에서 0번 부터 100번 까지 숫자가 몇 개 있는지 모두의 합을 구하려고 한다면 행렬(1,000 × 1,000)의 크기 × 검색 대상(100) 만큼 연산을 해야 하는데, 이는 1억 번의 연산을 하게 된다. DAT를 이용해서 각 숫자(0 ~ 100번)가 몇 번 등장했는지 2차원 배열의 요소를 입력 받으면서 바로 카운팅 하면 검색 대상의 합은 DAT 0번 부터 100번 까지만 배열에 방문해 각 요소를 모두 더하면 100번의 연산으로 문제를 해결할 수 있다.

• 변수 값 초기화

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());

// 배열의 크기 입력
int row = Integer.parseInt(st.nextToken());
int col = Integer.parseInt(st.nextToken());
// 배열에 담길 전체 요소의 개수 
int total_elements = row * col;

// 배열에 담을 입력 값이 한 줄로 들어온다고 가정
StringTokenizer st = new StringTokenizer(br.readLine());

int[] DAT = new int[101];

• 입력 받은 값을 하나씩 확인해서 DAT 배열에 카운팅 추가

for (int i=0; i<total_elements; i++) {
     int tmp = Integer.parseInt(st.nextToken());
     if (tmp > 100) continue;
     DAT[tmp]++;
 }

• 0 ~ 100번 이 몇 번 등장했는지 합을 구한 후 출력

int result = 0;
for(int i=0; i<101; i++) {
	result = result + DAT[i];
}

System.out.println(result);