[C.C.I] 01. 배열과 문자열

1.1 중복이 없는가?

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

문자열은 ASCII 문자열임을 가정하자. 문자 집합은 boolean 타입의 배열로 만들어서 i 번째 원소는 문자열에 해당 인덱스의 문자가 존재하는지를 확인한다. 배열의 길이는 128이 아니라 256이 되어도 괜찮다.

boolean isUniqueChars(String str) {
    if (str.length() > 128) return false;
    boolean[] charSet = new boolean[128];
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt[i];
        if (charSet[val]) return false;
        charSet[val] = true;
    }
    return true;
}

이 때 시간복잡도는 O(n)이고 공간복잡도는 O(1)이다. 단, 여기서 n은 문자열의 길이인데 128을 넘기지 않으므로 시간복잡도도 O(1)으로 볼 수 있다.

만약 자료구조를 추가로 사용할 수 없다면, 문자열 내의 각 문자를 다른 모든 문자와 비교한다. 이렇게 하면 시간복잡도는 O(n^2), 공간복잡도는 O(1)이다.

 

1.4 팰린드롬 순열

주어진 문자열이 희문(palindrome)의 순열인지 아닌지 확인하는 함수를 작성하라. 희문이란 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은 구절을 의미하며, 순열이란 문자열을 재배치 하는 것을 뜻한다. 희문이 꼭 사전에 등장하는 단어로 제한할 필요는 없다.

어느 방향으로 읽어도 같은 문자열이 되기 위해서는(희문의 순열) 어떤 조건이 필요할까? 거의 모든 문자가 각각 짝수 개 존재해서 절반은 왼쪽에, 절반은 오른쪽에 놓을 수 있으면 된다. 문자열의 길이가 홀수인 경우 한 개의 문자만 홀수 개이고, 문자열의 길이가 짝수 개라면 모든 문자의 갯수가 반드시 짝수여야 한다. 따라서 어떠한 문자열이 주어지더라도 회문이 되기 위해서는 홀수 문자가 하나여야 한다.

구현은 간단하다. 해시 테이블을 사용해서 각 문자가 몇 번이나 등장했는지 센다. 그 다음에는 해시 테이블을 훑어가며 홀수 문자가 한 개 이상인지 확인한다.

boolean isPermutationOfPalindrome(String phrase) {
    int[] table = buildCharFrequencyTable(phrase);
    return checkMaxOneOdd(table);
}

// 홀수 문자가 한 개 이상 존재하는지 확인
boolean checkMaxOneOdd(int[] table) {
    boolean foundOdd = false;
    for (int count : table) {
        if (count % 2 == 1) {
            if(foundOdd) return false;
            foundOdd = true;
        }
    }
    return true;
}

// 각 문자에 숫자를 대응시킨다.
int getCharNumber(Character c) {
    int a = Character.getNumericValue('a');
    int z = Character.getNumericValue('z');
    int val = Character.getNumericValue(c);
    if (a <= val && val <= z) {
        return val - a;
    }
    return -1;
}

// 각 문자가 몇 번 등장했는지 센다.
int[] buildCharFrequencyTable(String phase) {
    int[] table = new int[Character.getNumericValue('z') - Character.getNumericValue('a') + 1];
    for (char c : phrase.toCharArray()) {
        int x = getCharNumber(c);
        if (x != -1) {
            table[x]++;
        }
    }
    return table;
}

이 알고리즘은 시간복잡도가 O(N)이다.

 

1.9 문자열 회전

한 단어가 다른 문자열에 포함되어 있는지 판별하는 isSubstring이라는 메서드가 있다고 하자. s1과 s2의 두 문자열이 주어졌고, s2가 s1을 회전시킨 결과인지 판별하고자 한다(가령 'waterbottle'은 'erbottlewat'을 회전시켜 얻을 수 있는 문자열이다). isSubstring 메서드를 한 번만 호출해서 판별할 수 있는 코드를 작성하라.

s2가 s1을 회전한 결과라면 회전한 지점이 어디인지 알아야 한다. 회전은 s1을 x와 y로 분리한 후 s2가 되도록 재배치하는 것과 같다.

s1 = xy = 'waterbottle'

x = 'wat'

y = 'erbottle'

s2 = yx = 'erbottlewat'

따라서 s1을 x와 y로 나눈 뒤 xy = s1이 되고 yx = s2가 되는 방법이 있는지 확인하면 된다. 하지만 x와 y의 쪼개는 지점에 관계없이 yx는 언제나 xyxy의 부분 문자열이라는 사실을 알 수 있다. 즉, s2는 언제나 s1s1의 부분문자열이 된다.

따라서 간단하게 isSubString(s1s1, s2)를 호출하면 문제가 풀린다. 아래는 알고리즘을 구현한 코드이다.

boolean isRotation(String s1, String s2) {
	int len = s1.length();
    // s1과 s2의 길이가 같고 빈 문자열이 아닌지 확인한다.
    if (len == s2.length() && len > 0) {
    	// s1과 s1을 합친 결과를 새로운 버퍼에 저장한다.
        String s1s1 = s1 + s1;
        return isSubstring(s1s1, s2);
    }
    return false;
}

이 알고리즘의 수행시간은 isSubstring()의 수행시간에 따라 달라진다. isSubstring()의 수행시간이 O(A+B)라고 가정하면, isRotation의 수행시간은 O(N)이 된다.

 

참고자료

<코딩 인터뷰 완전 분석> 게일 라크만 맥도웰 저, 프로그래밍 인사이트 출판