[기본 java]#1 배열과 문자열 그리고 해시테이블

코딩테스트 준비 #1

자료구조

 

해시테이블

효율적인 탐색을 위한 자료구조로서 KEY를 VALUE에 대응시킴

아주 간단히 구현하는 경우, 배열과 해시함수만 있으면 됨

단 KEY에 대해서 해시 함수가 계산해 내는 정수값이 UNIQUE해야 함

 

UNIQUE를 고려하려면 배열을 크게 만들어야 하는데, 여기서 배열을 줄일 수 있는 방법은

hash(key)%array_length 위치에 연결리스트(linked list)형태로 저장하면 됨

 

단 이 경우 키 값을 갖는 객체를 찾아내려면 해당 키에 대한 연결리스트를 재 탐색 해야한다.

 

이때 이진 탐색 트리(binary search tree)를 사용해 해시 테이블을 구현할 수도 있는데 이렇게 하면 O(log n)시간 안에 탐색이 완료 되도록 할수 있다.

 

 

1. 간단한 hash테이블 구성

public HashMap<Integer, Student> buildMap(Student[] students) {
	HashMap<Integer, Student> map = new HashMap<Integer, Student>();
    	for (Student s: students) map.put(s.getId(), s);
    	return map;
   }

 

배열과 문자열 기본

2. ArrayList 사용

ArrayList는 동적으로 크기가 조절되는 배열로서, O(1)를 유지한다.

배열이 가득 차는 경우는 O(n)이지만, 자주 일어나는 일은 아니다.

public ArrayList<String> merge(String[] words, String[] more) {
	ArrayList<String> sentence = new ArrayList<String>();
    for (String w : words) sentence.add(w);
    for (String w : more) sentence.add(w);
    return sentence;
}

 

3. StringBuffer사용

단순하게 문자열 길이가 x이고, 문자열 개수가 n개라고 했을때 이 문자열 배열을 하나로 합친다면 O(x+2x+...+nx)가 되어 최종적으로는 O(xn^2)만큼의 시간이 걸린다. (아 나 python에서 그냥 이렇게 했었는데,,,,)

이런경우 StringBuffer를 사용하면 어느정도 이런 문제가 해결이된다.

StringBuffer는 모든 문자열의 배열을 미리 만들어 두고, 문자열 객체로의 복사는 필요할때 만 수행한다.

public String joinWords(String[] words) {
	StringBuffer sentence = new StringBuffer();
        for (String w : words) {
        sentence.append(w);
        }
        return sentence.toString();
}

 

기본도 어렵다.