1.배열과문자열

배열이나 문자열에 대한 문제들은 서로 대체 가능하다.

해시테이블

해시테이블은 효율적인 탐색을 위해 키를 값에 대응시킨 자료구조이다.

첫 번째 해시 테이블 구현방법
연결리스트와 해시 코드 함수로 구현

키(문자열 혹은 다른 어떤 자료형도 가능)와 값을 해시테이블에 넣을 때 상황 1. 키의 해시 코드를 계산
- 키의 자료형은 보통 int 혹은 long이 된다.
- 키의 개수는 무한한데 반해 int의 개수는 유한하기 때문에
  서로 다른 두 개의 키가 같은 해시 코드를 가리킬 수 있다.
  1. Hash(key) % array_length와 같은 방식으로 해시 코드를 이용해 배열의 인덱스를 구한다.
- 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리킬 수도 있다. 1. 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 존재한다.
- 충돌에 대비해서 반드시 연결리스트를 이용해야한다.
- 충돌이란 서로 다른 두 개의 키가 같은 해시 코드를 가리키거나
  서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 경우를 말한다.
키에 상응하는 값을 찾기 위한 과정 1. 주어진 키로 해시 코드를 계산 2. 해시 코드를 이용해 인덱스를 계산 3. 해당 키에 상응하는 값을 연결리스트에서 탐색
충돌이 자주 발생하는 경우
- 최악의 경우의 수행 시간(Worst case runtime)은 O(N) (N은 키의 개수)
- 일반적으로 해시에 대해 이야기 할 때 충돌을 최소화하도록 잘 구현된 경우 탐색 시간은 O(1)이다.

두 번째 해시테이블 구현 방법
균형 이진 탐색 트리(balanced binary search tree)로 구현된 탐색 시간은 O(logN)
크기가 큰 배열을 미리 할당해 놓지 않아도 되기 때문에 잠재적으로 적은 공간을 사용한다는 장점이 있다.
키의 집합을 특정 순서로 차례대로 접근가능한데 어떤 경우에는 이러한 기능이 유용하다.

ArrayList와 가변 크기 배열

자바의 배열(array)의 특징
- 배열의 길이가 고정되어 있다.
- 배열을 생성 시 배열의 크기를 함께 지정해야 한다.
동적 배열과 비슷한 자료구조가 필요한 경우 ArrayList를 사용
ArrayList의 특징
- 필요에 따라 크기를 변화시킬 수 있다.
- 데이터 접근 시간(access time) O(1)을 유지한다.
- 배열이 가득 차는 순간, 배열의 크기를 두 배로 늘린다.
  - 크기를 두 배 늘리는 시간 O(n)
  - 이런 일이 빈번하게 일어나지는 않기때문에 상환 입력 시간(amortized insertion time)으로 계산 했을 때 여전히 O(1)이 된다.
상환 입력 시간이 O(1)인 이유?
- 배열의 크기를 K로 늘리면 그 전에 배열의 크기는 K의 절반이었을것 이므로 K/2 만큼의 원소를 복사해야 한다.
- N개의 원소를 삽입 할 때 소요되는 작업은 O(N)이다.
- 배열의 상황에 따라 최악의 경우에 O(N)이 소요되는 삽입 연산도 존재하긴 하지만 평균적으로 각 삽입은 O(1)이 소요된다.

StringBuilder

문자열의 리스트(String[])가 주어쳤을때 이 문자열들을 하나로 이어붙일 때의 수행 시간은?
- 문자열을 이어붙일 때마다 두 개의 문자열을 읽어 문자를 하나하나 새로운 문자열에 복사해야한다.
- 총 수행시간은 O(N^2)이 된다.
  class Word { String joinWords(String[ ] words) { String sentence = ""; for (String w : words) { sentence = sentence + w; // 새로운 문자를 만듦 } return sentence; } }

StringBuilder를 사용하는 경우

가변 배열을 이용하는 경우 필요한 경우에 문자열을 복사하게끔 해준다.

class Word {
  String joinWords(String words) {
      StringBuilder sentence = new StringBuitder();
      for (String w : words) {
          sentence.append(w); // 
      }
      return sentence.toString();
  }
}

면접 문제

중복이 없는가? 에 대한 문제
- 해시 테이블을 이용하는 방법을 강구
- 비트 백터가 유용한가?
- O(NlogN) 시간에 풀 수 있는가? 그 해법은 무엇인가?
순열 확인 문제
- 두 문자열이 서로 순열관계에 있다는 말이 무엇인지 정리해보기
- 0(N1ogN) 시간의 해법이 하나 존재한다. 다른해법은 추가공간을 사용하지만 O(N) 시간이 걸린다.
- 해시테이블이 유용한가?
- 서로 순열관계에 있는 두 문자열은 같은 문자집합으로 이루어져있고, 그 순서만 다를 것이다. 순서도 같게 만들 수 있는가?
URL화 문제
- 문자열의 끝에서 시작해서 앞으로 읽어 나가면서 수정하는 것이 보통 가장 쉽다.
- 필요한 공백을 알아야 할지도 모른다. 하나씩 세어 볼 수 있는가?
회문 순열
- 모든 순열을 전부 생성할 필요가 없다. 아주 비효율적이다.
- 어떤 문자열이 회문의 순열일 때, 그 특성은 무엇인가?
- 해시 테이블을 사용해 본 적이 있는가? 0(N)시간으로 줄일 수 있다.
- 비트 벡터를 사용해서 공간을 줄일 수 있는가?
하나 빼기
- 쉬운 것부터 시작하라. 각각의 조건을 개별적으로 확인할 수 있는가?
- 문차를 삽입하는 것과 문자를 삭제하는 것 사이에는 어떤 연관성이 있는 가? 따로 확인해야 할 필요가 있는가?
- 세 가지 검증을 모두 한꺼번에 할 수 있는가?
문자열 압축
- 조심하라! 노드가 하나만 존재할 때도 처리했는가? 노드가 하나만 있을 때는 어떤 일이 발생하는가? 반환 값을 살짝 변경해야 할 수도 있다.
- 문자열을 반복해서 이어붙이지 않도록 조심하라. 아주 비효율적인 방법이다.
행렬 회전
- 배열을 감싸는 껍질(layer)별로 생각해보라. 특정 껍질을 회전시킬 수 있겠는가?
- 특정 껍질을 회전한다는 말은 네 개의 배열에서 값을 서로 바꾼다는 말이다.
- 배열이 두 개일 때 두 배열의 값을 맞바꿀 수 있는가? 이 방법을 네 개의 배열로 확장 할 수 있겠는가?
행렬
- 0을 찾을때마다 해당 행과 열을 삭제한다면, 전체 행렬이 모두 0이 될 가능성이 크다. 행렬을 수정하기 전에 0인 셀을 모두 찾기
- O(N^2) 대신 O(N) 공간을 추가로 사용할 수 있겠는가? 값이 0인 셀 리스트에서 진짜로 필요한 정보는 무엇인가?
- 0이 돼야 할 행과 열의 리스트를 유지하기 위해서 저장 장소가 필요할 수도 있다. 주어진 행렬을 저장 장소로 사용함으로써 필요한 추가 공간을 O(1)로 줄일 수 있겠는가?
문자열 회전
- 한 문자열이 다른 문자열의 회전된 결과라면, 특정 지점에서 회전을 했다는 뜻이다. 예를 들어 waterbottle의 3번째 문자에서 회전을 했다면, waterbottle의 3번째 문자에서 잘라낸 뒤
  오른쪽 절반(erbootle)을 왼쪽 절(wat) 이전에 놓은 것이다.
- firstCommonAncestor 함수는 p와 q가 같은 트리에 있고, 둘 다 null이 아닌 경우에, 이들의 첫 번째 공통 조상을 반환한다.
- 이전 힌트를 생각하여, erbottlewat 뒤에 erbottlewat를 이어붙이면 어떻게 되는지 생각해보기. erbottlewaterbottlewat가 된다.

PreviousCracking the Coding Interview Next2.연결리스트

Last updated 3 years ago

Was this helpful?