8일차

게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 p.133 ~ p. 136, 예제 1.1~1.3

내용 정리

9 면접 문제

01 배열과 문자열

해시테이블

해시테이블(hash table)은 효율적인 탐색을 위한 자료구조
키(key)를 값(value)에 대응시킨다.
연결리스트(linked list)와 해시 코드 함수(hash code function)로 구현할 수 있다.
키와 값을 넣는 과정
1. 키의 해시 코드를 계산한다. 키의 자료형은 보통 int 혹은 long.
2. hash(key) % array_length와 같은 방식으로 해시 코드를 이용해 배열의 인덱스를 구한다.
3. 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 존재한다. 키와 값을 해당 인덱스에 저장한다. 반드시 연결리스트릴 이용한다.
충돌 : 서로 다른 두개의 키가 같은 해시 코드를 가리키거나 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 경우
키의 개수는 무한하지만 int의 개수는 유한하기 때문에 발생할 수 있다.
키의 상응하는 값을 찾는 과정
1. 주어진 키로부터 해시 코드를 계산
2. 해시 코드를 이용해 인덱스를 계산
3. 키에 상응하는 값을 연결리스트에서 탐색
충돌이 자주 발생하면 최악의 경우 수행시간(Worst Case Runtime)은 O(N). 일반적으로는 O(1)
균형 이진 탐색 트리(balanced binary search tree)를 사용하는 방법은 탐색 시간이 O(logN)
크기가 큰 배열을 미리 할당하지 않아 잠재적으로 적은 공간을 사용하는 장점

ArrayList와 가변 크기 배열

어떤 언어는 배열의 크기를 자동으로 조절하지만 길이가 고정된 경우도 있다.
동적 가변 크기 기능이 내재되어 있는 배열과 비슷한 자료구조를 원할 떄는 보통 Arraylist를 사용한다.
필요에 따라 크기를 변화시킬 수 이씅면서도 O(1)의 접근 시간(access time)을 유지한다.
통상적으로 배열이 가득 차는 순간, 배열의 크기를 두 배로 늘린다.
두배로 늘리는 시간은 O(n)이지만 드물게 발생하기 때문에 상환 입력 시간(amortized insertion time)은 여전히 O(1)이다.

상환 입력 시간은 왜 O(1)이 되는가

크기가 N인 배열을 생각해보자. 이 배열은 이전에 크기가 N/2인 배열이 2배 늘어난 크기이다. 그 이전에는 N/4였을 것이다. 반복하면 1개부터 N개가 될때까지는 N/2 + N/4 + N/8 + … + 2 + 1, 즉 N보다 작다. 따라서 N개의 원소를 삽입할 때 소요되는 작업은 O(N)이다. 평균적으로는 O(1)이 소요된다.

StringBuilder

주어진 문자열의 리스트에 있는 이 문자열들을 하나로 이어 붙이려고 할 때 수행시간은 어떻게 되는가?

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

문자열을 이어붙일 때마다 두 개의 문자열을 읽어 들인 뒤 문자를 하나하나 새로운 문자열에 복사해야 한다. 처음에는 x개, 두번 째는 2x개, 세 번째는 3x개, n 번째는 nx개를 복사한다. 총 수행시간은 O(x+2x+3x+…+nx) = O(xn(n+1)/2) = O(xn^2)이 된다.

stringbuilder는 단순하게 가변 크기 배열을 이용해서 필요한 경우에만 문자열을 복사하게끔 해준다.

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

면접 문제

1.1 중복이 없는가

문자열이 주어졌을 때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라. 자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘 또한 고민하라.

답

def main(string):
    arr = list(string)
    arr_set = set(arr)
    if len(arr) != len(arr_set):
        return True
    else:
        return False

def main2(string):
    arr = list(string)
    for i in range(len(arr)):
        if arr[i] in arr[i+1:]:
            return True
    return False

1.2 순열 확인

문자열 두 개가 주어졌을 때 이 둘이 서로 순열 관계에 있는지 확인하는 메서드를 작성하라.

def main(a,b):
    for i in range(len(b)):
        if b[i] != a:
            return False
    return True

1.3 URL화

문자열에 들어 있는 모든 공백을 ‘%20’으로 바꿔 주는 메서드를 작성하라. 최종적으로 모든 문자를 다 담을 수 있을 만큼 충분한 공간이 이미 확보되어 있으며 문자열의 최종 길이가 함께 주어진다고 가정해도 된다

예제

입력: “Mr John Smith”, 13

출력: “Mr%20John%20Smith”

def main(s):
    arr = list(s)
    for i in range(len(s)):
        if arr[i] == ' ':
            arr[i] = '%20'
    return str(arr)

읽고 나서

해시테이블 면접에서 많이 물어보던데, 꼭 알아두자.

자료구조(1) 해시테이블

정의와 성질

8일차