책너두 (코딩 인터뷰 완전분석) 8일차 (~136p, 예제 1.1, 1.2, 1.3) 배열과 문자열 (1)

요약

• 면접 문제
  • 배열과 문자열
    • 해시 테이블
      • 구현을 위해 연결리스트와 해시 코드 함수가 필요함.
      • 충돌을 고려해야 함.
    • ArrayList와 가변 크기 배열
      • 적 가변 크기 기능이 내재되어있는 배열과 비슷한 자료구조를 원할 때 보통 ArrayList 를 사용함.
      • 상환 입력 시간은 왜 O(1)이 되는가
        • 배열 복제가 자주 일어나지 않기 때문
    • StringBuilder
      • 필요한 경우에만 문자열을 복제함.
    • 면접 문제

메모

9. 면접 문제

• www.CrackingTheCodingInterview.com 에서 전체 해법을 다운 받을 수 있음.

01. 배열과 문자열

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

해시 테이블

• 효율적인 탐색을 위한 자료구조로서 키를 값에 대응시킴.
• 간단한 해시테이블을 구현하기 위해선 연결리스트와 해시 코드 함수만 있으면 됨.
• 키값을 해시테이블에 넣는 과정
  1. 키의 해시 코드를 계산한다.
     • 키의 자료형은 보통 int, long 이 됨 (문자열 혹은 다른 어떤 자료형도 가능함)
     • 키의 개수는 무한하지만 int 개수는 유한하므로 서로 다른 두 개의 키가 같은 해시 코드를 가리킬 수 있음.
  2. hash(key) % array_length 와 같은 방식으로 해시 코드를 이용해 배열의 인덱스를 구함.
     • 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리킬 수도 있음.
     • ex) 11 % 10 = 21 % 10
  3. 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 존재함.
     • 충돌에 대비해서 반드시 연결리스트를 이용해야 함.
     • 충돌이란,
       1. 서로 다른 두 개의 키가 같은 해시 코드를 가리킴.
       2. 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 경우를 말함.

• 키에 대응하는 값을 찾으려면 다음의 과정을 반복해야 함.
  • 주어진 키로 해시코드를 계산한다
  • 이 해시 코드로 인덱스를 계산한다.
  • 해당 키에 상응하는 값을 연결 리스트에서 탐색한다.
• 충돌이 자주 발생한다면, 최악의 경우 수행 시간이 O(N)이 된다. (N = 키의 개수)
• 또 다른 방법으로, 균형 이진 탐색 트리를 사용하는 방법이 있음.
  • 탐색 시간이 O(logN)이 됨.
  • 이 방법은 크기가 큰 배열을 미리 할당해 놓지 않아도 되기 때문에 잠재적으로 적은 공간을 사용한다는 장점이 있음.
  • 키의 집합을 특정 순서로 차례대로 접근할 수 있어서 어떤 경우에는 유용함.

ArrayList와 가변 크기 배열

• 특정 언어에서 배열의 크기를 자동으로 조절할 수 있음.
  • ex) python
  • 데이터를 덧붙일 때마다 배열 혹은 리스트의 크기가 증가함
• 하지만 자바 같은 언어에서는 배열의 길이가 고정되어 있음.
  • 이 경우, 배열을 만들 때 배열의 크기를 함께 지정해야 함.
• 동적 가변 크기 기능이 내재되어있는 배열과 비슷한 자료구조를 원할 때 보통 ArrayList 를 사용함.
  • 필요에 따라 크기를 변화시킬 수 있고 O(1)의 접근 시간을 유지함.
• 통상적으로 배열이 가득 차면 배열 크기를 두 배로 늘림.
  • 크기를 두 배로 늘리는 시간은 O(N) 이지만, 자주 발생하는 일이 아님.
  • 따라서, 상환 시간으로 계산하면 여전히 O(1)이 됨.
  • 이러한 배열/리스트에 대해서 익숙해야 함.
    • 언어마다 자료구조 이름이나 배열 크기 조절인자(자바는 2)는 달라질 수 있음.

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

• 크기가 N 인 배열의 경우, 그 전 배열의 크기는 N/2 만큼 의 원소를 복사했을 것이다.
• 따라서 N 개의 원소를 삽입하기 위해 복사해야 하는 원소의 총 개수는 N/2 + N/4 + N/8 + … + 2 + 1, 이므로 즉 N 보다 작음.
• 따라서, N 개의 원소를 삽입할 때 소요되는 작업은 O(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^2) = O(n^2) 이 됨.
• StringBuilder를 사용하면 가변 크기 배열을 이용해서 필요한 경우에만 문자열을 복사하게 해줌.

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

• 문자열, 배열, 일반적인 자료구조를 연습해 보는 가장 좋은 방법은 자신만의 StringBuilder, HashTable, ArrayList 를 구현해 보는 것임.

참고 : 해시테이블 충돌 해결 방법 (p814) / Rabin-Karp 문자열 탐색 알고리즘(p815)

면접 문제

1.1 중복이 없는가

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

public class Solution {
    public static boolean isUnique(String s) {
        Set<Character> chars = new HashSet<>();
        for (char c : s.toCharArray()) {
            if (chars.contains(c)) {
                return false;
            }
            chars.add(c);
        }
        return true;
    }

    public static void main(String[] args) {
        String[] words = {"abcde", "hello", "apple", "kite", "padle"};
        for (String word : words) {
            System.out.println(word + ": " + isUnique(word));
        }
    }
}

abcde: true
hello: false
apple: false
kite: true
padle: true

1.2 순열 확인

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

public class Solution {
    private static String sort(String s) {
        char[] charArray = s.toCharArray();
        Arrays.sort(charArray);
        return new String(charArray);
    }

    public static boolean isPermutationRelation(String s1, String s2) {
        return sort(s1).equals(sort(s2));
    }

    public static void main(String[] args) {
        String[][] pairs = {{"apple", "papel"}, {"carrot", "tarroc"}, {"hello", "llloh"}};
        for (String[] pair : pairs) {
            String word1 = pair[0];
            String word2 = pair[1];
            boolean anagram = isPermutationRelation(word1, word2);
            System.out.println(word1 + ", " + word2 + ": " + anagram);
        }
    } 
}

1.3 URL화

• 문자열에 들어 있는 모든 공백을 '%20'으로 바꿔 주는 메서드를 작성하라. 최종적으로 모든 문자를 다 담을 수 있을 만큼 충분한 공간이 이미 확보되어 있으면 문자열의 최종 길이가 함께 주어진다고 가정해도 된다. (자바로 구현한다면 배열 안에서 작업할 수 있도록 문자 배열(character array)를 이용하길 바란다.)

public class Solution {
    private static final String blank = "%20";

    public static void main(String[] args) {
        String s = "Mr John Smith    ";
        System.out.println(makeURL(s));
    }

    static public String makeURL(String s) {
        String[] splitString = s.split(" ");
        return Arrays.stream(splitString).collect(Collectors.joining(blank));
    }
}