Chapter1 Arrays and Strings

[Hash Tables]

 해쉬테이블은 key를 이용하여 value를 저장하는 자료구조이다. 해쉬란 수학적인 연산을 통해 최대한 중복되지않는 값을 만드는것이다. 좋은 해쉬알고리즘은 가능한한 중복된 값을 최소화 하는 해쉬 알고리즘이다. 때문에 보통 이런 해쉬 자료구조에서의 탐색 시간복잡도는 O(1)의 시간을 갖는다. 하지만 해쉬 알고리즘에 의해 동일한 key가 생성된다면 여러가지 방법으로 이를 처리한다. 대표적인것이 충돌시(중복된 key값을 해쉬에 의해 만들어내는것) 2개의 해쉬알고리즘을 사용하는것이고 두번째는 충돌이 발생할시 이를 순서대로 연결리스트로 저장하는것이다. 

다음의 코드는 Integer 타입을 key로하고 Student 객체를 value로 하는 해시맵 자료구조를 사용하여 입력받은 Student 배열을 해시자료구조에 삽입하는 메서드이다.

[ArrayList(Dynamically Resizing Array)]

 ArrayList는 말그대로 내부적으로 배열 자료구조를 사용한 List이다. Dynamically Resizing Array라고 하는것은 사용자가 ArrayList를 이용하여 삽입/삭제 연산시에 내부적인 배열 사이즈를 고려하지않아도 동적으로 조절되기 때문이다. 사용자가 ArrayList에 엘리먼트를 삽입하게되면 배열이 꽉찬경우 길이가 2배 더 큰 배열을 만들어 이를 복제한다. 때문에 이러한 비용이 상당히 크다는것을 알고있어야한다. 

[String, StringBuffer, StringBuilder]

*String : String은 immutable하다고 한다. 이는 수정할 수 없고 불변이라는 소리인데 무슨 소리인가 하면 String에 할당된 값은 수정(String값 변경)시에 동일한 메모리 주소에서 값이 수정되는게 아닌 아얘 다른 메모리 주소를 갖게되고 새로 생성된다는 뜻이다. (만약 String을 리터럴을 이용하여 생성하게 되고 값이 동일한 다른 변수에 할당시에는 같은 주소값을 같게된다.)

String str = "개발자";
String str2 = new String("개발자"); // str주소값 != str2주소값
String str3 = "개발자"; // str주소값 == str3주소값
String str4 = new String("개발자"); // str2주소값 != str4주소값
/*
 new를 사용하지않고 스트링을 생성하는것을 문자 리터럴이라고 하는데 이렇게 생성을 한 값들은 String pool 이라는곳에 저장이 된다.
(String pool은 JVM 런타임 메모리 영역중 Class영역에 있다.)
때문에 동일한 값을 갖는(str3같은) 값을 할당시에는 메모리를 효율적으로 사용하기 위해 같은 주소값을 참조한다.
반면 new를 이용한 String을 생성시엔 동일한 값이라 하여도 다른 주소값을 할당한다.(JVM 메모리 영역중 Heap영역에 생성이 된다.)
*/

*StringBuffer,StringBuilder : 이 둘의 공통점은 위의 String과는 다르게 mutable하다는 것이다.  
때문에 문자열을 합치거나 뒤에 추가하여 붙일때 그냥 String을 사용한것보다 효율적이다. 그렇다면 둘다 mutable한데 이 둘은 무슨 차이가 있을까?
이둘의 차이점은 동시 접근을 허용하는가 안하는가의 차이 이다. StringBuffer같은 경우는 메서드에 syncrosized 키워드가 붙어있다. 
때문에 다중 쓰레드 환경에서 동시에 이 모듈을 사용할 수 없어 안전하다.
하지만 StringBuilder는 다중 쓰레드 환경에서 동시에 접근이 가능하기 때문에 의도치 않은 결과가 나올 수 있다. 
때문에 StringBuffer는 비동기인 작업을 하거나 다중 쓰레드를 사용할때 적합하고 StringBuilder는 그렇지 않은 경우에 쓰기 좋다.

위의 코드의 시간복잡도는 얼핏보면 O(n)이지만 실제로는 O(n^2)이다. StringBuffer는 내부적으로 String을 char[]로 처리하기 때문에 sentence.apeend(w)에서 w의 길이만큼 char를 하나씩 뒤에 붙어가며 처리한다. 때문에 내부적으로 반복문을 한번 더 돌기 때문에 O(n^2)의 시간복잡도를 갖는것이다.

[Interview Questions]

1.1 추가적인 자료구조를 사용하지 않고 주어진 문자열의 모든 단어가 유니크한지 아닌지를 판별하는 알고리즘을 작성하라.

1.2 주어진 문자열을 뒤집어 출력하는 알고리즘을 작성하라.

1.3 추가 버퍼를 사용하지않고 주어진 문자열에서 중복된 문자를 제거하는 알고리즘을 작성하라.

1.4 주어진 두 문자열이 아나그램인지 아닌지를 판별하는 알고리즘을 작성하라.(아나그램은 문자열을 뒤집은것을 말한다.)

1.5 주어진 String에서 space(' ')를 모두 '%20'으로 바꾸는 알고리즘을 작성하라.

해당 모듈의 시간복잡도는 O(n^2)이다. 공간복잡도를 포기하는대신 시간복잡도를 개선을 위해서 아이디어를 생각해보자면 버퍼를 만들어두어 공백문자의 인덱스 위치만 기억해둔뒤 해당 버퍼를 이용해서 기존 문자는 새로 복제하면서 기억해뒀던 인덱스 위치에만 %20을 넣어 O(n)으로 만들 수 있을것 같다. append연산은 내부적으로 할대마다 배열의 복제 및 쉬프트 연산이 이뤄지기 때문에 실제로 성능개선을 위해선 미리 인덱스 위치를 파악해두는 작업을 한뒤 String을 생성하는것이 좋아보인다.

1.6 각 픽셀이 4byte인 nxn으로 이루어진 배열을 90도 회전하는 알고리즘을 작성하라.

1.7 MxN으로 이루어진 2차원 배열을 0으로 초기화하는 알고리즘을 작성하라.

1.8 주어진 두 문자열(s1, s2)이 있을때 s1을 한번만 substring하여 s2를 만들 수 있는지 판별하는 알고리즘을 작성하라.

#원문

 [Cracking the coding interview PDF]