[Coding Interview University] 배열 : 이론 및 구현

<본 블로그는 코딩인터뷰대학 님의 Git과 서적을 참고해서 공부하며 작성하였습니다 :-)>

 

🫧 배열과 문자열

❤️ 해시테이블 (hash table)

: 효율적인 탐색을 위한 자료구조로서, key를 value 에 대응시킴

: 최악의 경우 O(n) // n은 키의 개수

: 최선의 경우 O(1)

 

1) 키의 해시 코드 계산

• 키의 자료형은 보통 int or long
• 키의 개수 무한 (int 는 유한)

2) hash(key) % array_length 방식으로 해시 코드 이용해 배열의 인덱스 구함

• 서로 다른 두 개의 해시 코드가 같은 인덱스 가리킬 수 있음

3) 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트 존재

• 키와 값을 해당 인덱스에 저장 (반드시 연결리스트 이용!)
• 💥 충돌 : 서로 다른 두 개의 키가 같은 코드를 가리키거나, 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 경우

⇒ 키에 상응하기 위해서 위를 반복!

⇒ 주어진 키로부터 해시 코드를 계산, 해시 코드를 이용해 인덱스 계산, 해당 키에 상응하는 값을 연결 리스트에서 탐색

균형 이진 탐색 트리 (balanced binary search tree)
: 탐색 시간은 O(logN)
: 크기가 큰 배열을 미리 할당해 놓지 않아도 되기 때문에 적은 공간 사용 가능
: 키의 집합을 특정 순서대로 접근 가능

 

❤️ ArrayList 와 가변 크기 배열

• 동적 가변 크기 기능 내재의 배열일 때 사용
• 필요에 따라 크기를 변화 가능
• O(1)의 접근 시간을 유지
• 배열이 가득 차면, 배열의 크기를 두 배로 늘림
  • O(n)으로 늘려지지만, 상환 입력 시간으로 인해 O(1)
  • n개의 원소를 삽입할 때 소요 작업은 O(n)
  • 평균적으로 각 삽입은 O(1)

 

❤️ StringBuilder

: 가변 크기 배열을 이용해서 필요한 경우에만 문자열 복사

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

 

 

🫧 벡터 구현하기

➡️ size() - 항목의 개수

public static void main(String[] args){
    ArrayList<Object> sizeTest = new ArrayList<Object>();
    System.out.println( sizeTest.size() );  // 0
}

➡️ capacity() - 들어갈 수 있는 항목의 최대 개수

public static void main(String[] args) {
    StringBuffer buff = new StringBuffer(20);
    buff.append("GwangJik");
    System.out.println("Capacity : " + buff.capacity());    // 20
}

➡️ is_empty()

String test = null;
if(test != null && test.isEmpty()) {
    System.out.println(test);
}

➡️ at(index) - 인덱스에 있는 항목을 돌려주고, 인덱스가 범위 밖이면 에러를 냄

int digitStr = "456";

// 0번째에 있는 char 값을 리턴
digitStr.charAt(0) // 4

➡️ push(item)

var fruit = ["사과", "배", "포도"];
fruit.push("딸기");      // 배열 뒤쪽에 데이터 삽입 ["사과", "배", "포도", "딸기"]

➡️ insert(index, item) - index에 item을 삽입하고 기존 인덱스의 값부터 쭉 오른쪽으로 쉬프트

public class ArrayListDemo {
    public static void main(String[] args)
    {
        // create an empty list with an initial
        // capacity
        List<String> list = new ArrayList<String>(5);
 
        // use add() method to initially
        // add elements in the list
        list.add("Geeks");
        list.add("For");
        list.add("Geeks");
       
        // Add a new element at index 0
        list.add(0, "Hello");
       
        // prints all the elements available in list
        for (String str : list) {
            System.out.print(str + " ");
        }
    }
}
// Hello Geeks For Geeks

➡️ prepend(item) - 맨 앞에 원소를 삽입

int[] arr = { 10, 20, 30 };

arr = ArrayUtils.add(arr, 40);

➡️ pop() - 마지막 원소를 삭제하고 값을 돌려준다

var fruit = ["사과", "배", "포도"];
fruit.pop();             // 배열 뒤쪽의 데이터 제거 ["사과", "배"]

➡️ delete(index) - delete item at index, shifting all trailing elements left

import java.io.File;  // Import the File class

public class DeleteFile {
  public static void main(String[] args) { 
    File myObj = new File("filename.txt"); 
    if (myObj.delete()) { 
      System.out.println("Deleted the file: " + myObj.getName());
    } else {
      System.out.println("Failed to delete the file.");
    } 
  } 
}

// Deleted the file: filename.txt

➡️ remove(item) - looks for value and removes index holding it (even if in multiple places)

String[] fruitsArray = {"apple", "banana", "kiwi", "mango"};
ArrayList<String>  fruits = new ArrayList<>(Arrays.asList(fruitsArray));
System.out.println("all: " + fruits.toString());

String returned = fruits.remove(2);
System.out.println("remove(2): " + fruits.toString());
System.out.println("returned: " + returned);

// all: [apple, banana, kiwi, mango]
// remove(2): [apple, banana, mango]
// returned: kiwi

➡️ find(item) - looks for value and returns first index with that value, -1 if not found

import java.util.regex.Matcher;  
import java.util.regex.Pattern;  
  
public class BooleanFindMethodExample1 {  
    public static void main(String[] args) {  
        // TODO Auto-generated method stub  
        Pattern p=Pattern.compile("java");  
        Matcher m=p.matcher("HellojavaHellojava");  
        int c=0;  
        // finding matching char   
        while(m.find())  
        {  
        c=c+1;  
        System.out.println("Start position of matching String "+m.start());  
        System.out.println("End position of Matching String (java) "+m.end());  
        }  
        System.out.println(" Number of matches : "+c);  
    }  
}

Pattern pat = Pattern.compile("여기에 정규식 입력"); 
패턴을 정의 한 후

Matcher match = pat.matcher("여기에 조사할 문자열");
정의된 패턴에 매치 되는 값을 저장한다.

match.find()
매치된 값이 있으면 true 없으면 false를 반환한다.

match.group()
매치된 값을 반환한다.

➡️ resize(new_capacity) // private 함수

• 용량이 꽉 차면, 그 두배로 크기를 조정한다
• item을 하나 꺼낼 때, 용량이 1/4이라면, 용량을 절반으로 줄인다