[코딩 인터뷰 완전 분석] 자료구조 / 배열과 문자열

해시테이블 (hash table)

효율적인 탐색을 위한 자료구조로서 key를 value에 대응시키는 것. 구현하는 방법은 여러 가지가 있는데, 연결리스트와 해시 코드 함수를 통해 간단한 해시 테이블을 구현한다. key는 문자열 혹은 어떤 자료형도 가능하다.

 

1. key의 hash code를 계산한다. 키의 자료형은 보통 int나 long이 된다. 
   key의 개수는 무한한데, int의 개수는 유한하기 때문에 서로 다른 두 개의 키가 같은 해시 코드를 가리킬 수 있음.
2. hash(key) % array_length와 같은 방식으로 해시 코드를 이용해 배열의 인덱스를 구한다. 물론 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리킬 수도 있음.
3. 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 존재한다. 키와 값을 해당 인덱스에 저장한다. 충돌에 대비해서 반드시 연결리스트를 이용해야 한다. 여기서 충돌이란 서로 다른 두 개의 키가 같은 해시 코드를 가리키거나 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 경우를 말한다. 

주어진 키로부터 해시 코드를 계산하고, 이 코드를 이용하여 인덱스를 계산한다. 그 다음 해당 키에 상응하는 값에 상응하는 값 연결리스트에서 탐색하면 된다. 

충돌이 자주 발생한다면, 최악의 경우의 수행 시간은 O(n) (n은 키의 개수)가 된다. 일반적으로는 충돌을 최소화하도록 잘 구현된 경우를 가정하는데 이 경우에 탐색 시간은 O(1)이다. 

 

★★ ArrayList와 가변 크기 배열

특정 언어에선, 배열의 크기를 자동으로 조절할 수 있다. 데이터를 덧붙일 때마다 배열 혹은 리스트의 크기가 증가한다. 

하지만 자바 같은 언어에서는 배열의 길이가 고정되어 있다. 이런 경우에는 배열을 만들 때 배열의 크기를 함께 지정해야 한다. 

 

동적 가변 크기 기능이 내재되어 있는 배열과 비슷한 자료구조를 원할 때는 보통 ArrayList를 사용한다. 필요에 따라 크기를 변화시킬 수 있으면서도 O(1)의 접근 시간을 유지한다. 배열이 가득차는 순간, 배열의 크기를 두 배로 늘린다.

크기를 두 배 늘리는 시간은 O(n)이지만, 자주 발생하는 일은 아니기 때문에 amortized insertion time으로 계산하면 O(1)이다. 

 

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

자바 https://programmers.co.kr/learn/courses/17/lessons/805

 

사용하는 언어에 관계없이, 동적 가변 크기 배열/리스트에 대해서 익숙해져 있어야 한다. 

 

StringBuilder

문자열의 리스트가 주어졌을 때 이 문자열들을 하나로 이어 붙이려고 한다. 이 때의 수행시간을 구해보자.

모든 문자열의 길이(x)가 같은 n개의 문자열이 주어졌다고 가정한다.

 

String joinWords(String[] words){
	String sentence="";
	for (String w:words) {
		sentence = sentence + w;
	}
	return sentence;
}

문자열을 이어붙일 때마다 두 개의 문자열을 읽어 들인 뒤 문자를 하나하나 새로운 문자열에 복사해야 한다.

처음에는 x개, 두 번째는 2x개, 세 번째는 3x개, n번째는 nx개의 문자를 복사해야 한다. 총 수행 시간은 O(x+2x+...+nx), 즉 O(nx^2)이 된다. 

 

이를 해결하기 위해, StringBuilder를 사용한다. 단순하게 가변 크기 배열을 사용하여 필요한 경우에만 문자열을 복사하게끔 해준다.

 

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