배열, 문자열( Array and String)

[코딩 인터뷰 완전 분석]

 

▶ 해시 테이블

   - 효율적인 탐색을 위한 자료구조로 키를 값에 대응 시킨다.

   해시 테이블을 구현하기 위해서는 연결리스트와 해시코드 함수만 있으면 된다.

   - 키와 값을 해시테이블에 넣을때 다음의 과정을 거친다.

    1. 키의 해시코드를 계산한다.

      ※키의 개수는 무한대인데, int나 long의 개수는 유한하기때문에 서로 다른 두 개의 키가 같은 해시코드를 

        가리킬 수 있다는 사실을 명심해야한다.

    2. hash(key) % array_length와 같은 방식으로 해시코드를 이용해 배열의 인덱스를 구한다.

     -> 같은 인덱스를 가르킬수 있다.

    3. 배열의 각 인덱스는 키와 같은 같은 값으로 이뤄진 연결리스트가 존재한다.

        - 키와 값을 해당 인덱스에 저장한다.

        - 충돌에 대비하여 연결리스틀 이용해야한다.

주어진 키로 부터 해시코드를 계산하고, 이 해시코드를 이용해서 인덱스를 계산한다.

    최악의 경우 : O(N)

    충돌 최소 경우 : O(1)

또 다른, 방법으로는 균형 이진 탐색을 이용하는 방법이다. O(logN)

 -> 이 방법은 크기가 큰 배열을 미리 할당해 놓지 않아도 잠재적으로 적은 공간을 사용한다는 장점이 있다.

 

▶ ArrayList와 가변 배열

   -> 데이터를 덧붙일때마다 배열 혹은 리스트의 크기가 증가 한다.

   접근 시간 : O(1)

   크기를 늘렸을때의 시간은 O(N)이지만 자주 발생하지 않기 때문에 삽입 시간은 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);
   return sentence;
   }

 

▶ StringBuilder

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

문자열을 읽을 때마다 두 개의 문자열을 읽어드린뒤 새로운 문자열에 복사해야하기 때문에 수행시간은

O(N^2)가 된다.

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