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)이 된다.
참고자료
<코딩 인터뷰 완전 분석> 게일 라크만 맥도웰 저, 프로그래밍 인사이트 출판
'Computer Sci. > Algorithms' 카테고리의 다른 글
| [알고리즘 문제 해결 전략] Ch03-3. 알고리즘 설계 패러다임 (동적 계획법) (0) | 2022年05月25日 |
|---|---|
| [C.C.I] 02. 연결리스트 (0) | 2022年04月29日 |
| [알고리즘 문제 해결 전략] Ch03-2. 알고리즘 설계 패러다임 (분할 정복) (0) | 2022年03月21日 |
| [알고리즘 문제 해결 전략] Ch03-1. 알고리즘 설계 패러다임 (브루트 포스) (0) | 2022年03月11日 |
| [알고리즘 문제 해결 전략] Ch02. 알고리즘 분석 (1) | 2022年03月04日 |