Ch01 Array and Strings
1.1 문자열에 포함된 다른 문자들이 전부 유일한지를 검사하는 알고리즘 구현. 다른 자료구조를 사용할 수 없는 상황에서의
문자가 a~z로 총 26개라면 int 변수 1개로 count해서 이를 판별할 수 있다.
Code
public class QuestionB {
/* Assumes only letters a through z. */
public static boolean isUniqueChars(String str) {
if (str.length() > 26) { // Only 26 characters
return false;
}
int checker = 0;
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i) - 'a';
if ((checker & (1 << val)) > 0) return false;
checker |= (1 << val);
}
return true;
}
public static void main(String[] args) {
String[] words = {"abcde", "hello", "apple", "kite", "padle"};
for (String word : words) {
System.out.println(word + ": " + isUniqueChars(word));
}
String a = "abcde";
}
}
1.2 Permuation을 확인 하는 방법, Anagram 이랑 동일
정렬된 Algorihtm을 가지고 비교 한다.
Sroting을 해서 비교하는 방법이다.
public class QuestionA {
public static String sort(String s) {
char[] content = s.toCharArray();
java.util.Arrays.sort(content);
return new String(content);
}
public static boolean permutation(String s, String t) {
return sort(s).equals(sort(t));
}
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 = permutation(word1, word2);
System.out.println(word1 + ", " + word2 + ": " + anagram);
}
}
}Ascii 코드를 이용한 방법이다.
public class QuestionB {
public static boolean permutation(String s, String t) {
if (s.length() != t.length()) return false; // Permutations must be same length
int[] letters = new int[128]; // Assumption: ASCII
for (int i = 0; i < s.length(); i++) {
letters[s.charAt(i)]++;
}
for (int i = 0; i < t.length(); i++) {
letters[t.charAt(i)]--;
if (letters[t.charAt(i)] < 0) {
return false;
}
}
return true; // letters array has no negative values, and therefore no positive values either
}
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 = permutation(word1, word2);
System.out.println(word1 + ", " + word2 + ": " + anagram);
}
}
}1.3 URLify 모든 빈 공간을 %20으로 채워라
예제
input: "Mr John Smith "
Output: "Mr%20John%20Smith"
뒷 쪽에 충분한 Margin이 있으므로 뒤에서 부터 앞으로 작업하는 것이 일반적인 방법이다.
two scan approach를 채택 한다.
- 첫 번째에서는 number of spaces를 카운트 한다. 그 다음 3배를 해서 최종적으로 얼마나 많은 추가 character가 필요한지 알 수 있다.
- 두 번째에서는 실제
string의 순서를 조절하게 된다. 즉 space가 있으면 %20을 채우고 no space면 orignal character를 채운다.
# O(N)
import unittest
def urlify(string, length):
'''function replaces single spaces with %20 and removes trailing spaces'''
new_index = len(string)
for i in reversed(range(length)):
if string[i] == ' ':
# Replace spaces
string[new_index - 3:new_index] = '%20'
new_index -= 3
else:
# Move characters
string[new_index - 1] = string[i]
new_index -= 1
return string
class Test(unittest.TestCase):
'''Test Cases'''
# Using lists because Python strings are immutable
data = [
(list('much ado about nothing '), 22,
list('much%20ado%20about%20nothing')),
(list('Mr John Smith '), 13, list('Mr%20John%20Smith'))]
def test_urlify(self):
for [test_string, length, expected] in self.data:
actual = urlify(test_string, length)
self.assertEqual(actual, expected)
if __name__ == "__main__":
unittest.main()문자열 압축 (String Compression)
# O(N)
import unittest
def string_compression(string):
compressed = []
counter = 0
for i in range(len(string)):
if i != 0 and string[i] != string[i - 1]:
compressed.append(string[i - 1] + str(counter))
counter = 0
counter += 1
# add last repeated character
compressed.append(string[-1] + str(counter))
# returns original string if compressed string isn't smaller
return min(string, ''.join(compressed), key=len)
class Test(unittest.TestCase):
'''Test Cases'''
data = [
('aabcccccaaa', 'a2b1c5a3'),
('abcdef', 'abcdef')
]
def test_string_compression(self):
for [test_string, expected] in self.data:
actual = string_compression(test_string)
self.assertEqual(actual, expected)
if __name__ == "__main__":
unittest.main()Rotate Matrix
Matrix를 Rotation 하게 된다. 외부에서 안으로 진행하는 방식으로 처리 한다.
# O(NxN)
import unittest
def rotate_matrix(matrix):
'''rotates a matrix 90 degrees clockwise'''
n = len(matrix)
for layer in range(n // 2):
first, last = layer, n - layer - 1
for i in range(first, last):
# save top
top = matrix[layer][i]
# left -> top
matrix[layer][i] = matrix[-i - 1][layer]
# bottom -> left
matrix[-i - 1][layer] = matrix[-layer - 1][-i - 1]
# right -> bottom
matrix[-layer - 1][-i - 1] = matrix[i][- layer - 1]
# top -> right
matrix[i][- layer - 1] = top
return matrix
class Test(unittest.TestCase):
'''Test Cases'''
data = [
([
[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20],
[21, 22, 23, 24, 25]
], [
[21, 16, 11, 6, 1],
[22, 17, 12, 7, 2],
[23, 18, 13, 8, 3],
[24, 19, 14, 9, 4],
[25, 20, 15, 10, 5]
])
]
def test_rotate_matrix(self):
for [test_matrix, expected] in self.data:
actual = rotate_matrix(test_matrix)
self.assertEqual(actual, expected)
if __name__ == "__main__":
unittest.main()1.7 M x N 행렬의 한 원소가 0일 경우 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘을 작성
생각1
단순히 발견하는 0의 행과 열을 0으로 변경하면서 진행하면 금방 전부다 0이 되어 버린다.
생각2
추가적인 공간 O(MN)에 0의 위치를 기록하고 그 다음 해당 열과 행을 0으로 초기화 하는 방법이 있다.
생각3
그런데 정말로 O(MN) 만큼의 공간이 필요한가? 그렇지 않다. 같은 행과 열의 모든 원소의 값을 0으로 만들 것이므로, 0인 원소가 정확히 몇 번째 행에 몇 번째 열의 원소였는지 알 필요는 없다. 우리는 그저 어떤 행 안에 0 값을 갖는 원소가 있다는 사실만 기록하면 되고, 어떤 열 안에 0값을 갖는 원소가 있다는 사실만 기록하면 된다. 어차피 그 행과 열의 모든 원소를 0으로 만들 것인데, 왜 정확한 위치를 기록해야 하는가.
코드는 아래와 같다. 0이 있는 행과 열을 추적하기 위한 배열을 두 개 사용 했다. 그런 다음, 이 배열의 갑에 따라서 행과 열을 전부 0으로 만들도록 했다.
코드
# O(MxN)
import unittest
def zero_matrix(matrix):
m = len(matrix)
n = len(matrix[0])
rows = []
cols = []
for x in range(m):
for y in range(n):
if matrix[x][y] == 0:
rows.append(x)
cols.append(y)
for row in rows:
nullify_row(matrix, row)
for col in cols:
nullify_col(matrix, col)
return matrix
def nullify_row(matrix, row):
for i in range(len(matrix[0])):
matrix[row][i] = 0
def nullify_col(matrix, col):
for i in range(len(matrix)):
matrix[i][col] = 0
class Test(unittest.TestCase):
'''Test Cases'''
data = [
([
[1, 2, 3, 4, 0],
[6, 0, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 0, 18, 19, 20],
[21, 22, 23, 24, 25]
], [
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[11, 0, 13, 14, 0],
[0, 0, 0, 0, 0],
[21, 0, 23, 24, 0]
])
]
def test_zero_matrix(self):
for [test_matrix, expected] in self.data:
actual = zero_matrix(test_matrix)
self.assertEqual(actual, expected)
if __name__ == "__main__":
unittest.main()1.8 한 단어가 다른 단어에 포함된 문자열인지 판별하는 isSubstring이라는 메서드가 있다고 하자. s1과 s2의 두 문자열이 주어졌을 때, s2가 s1을 회전시킨 결과인지 판별하는 코드를 isSubstring을 한 번만 호출하도록 하여 작성하라.
s2가 s1을 회전시켜 얻은 문자열이라면, 회전된 지점이 어딘지를 알아봐야 한다.
가령 waterbottle을 회전시켜 erbbottlewat을 얻어다고 해보자.
회전시킬 때, s1을 x와 y의 두 부분으로 나눈 다음 다시 배열하여 s2를 얻었을 것이다.
s1 = xy = waterbottle
x = wat
y = erbottle
s2 = yx = erbottlewat
하지만 중요한점은 x와 y를 나눈 지점이 어디인가 상관없이, yx는 언제나 xyxy의 부분 문자열이다. 다시 말해서, s2는 언제나 s1s1의 부분 문자열이란 이야기이다.
즉, isSubstring(s1s1,s2)인지 알아보면 된다는 것이다.
# O(N)
import unittest
def is_substring(string, sub):
return string.find(sub) != -1
def string_rotation(s1, s2):
if len(s1) == len(s2) != 0:
return is_substring(s1 + s1, s2)
return False
class Test(unittest.TestCase):
'''Test Cases'''
data = [
('waterbottle', 'erbottlewat', True),
('foo', 'bar', False),
('foo', 'foofoo', False)
]
def test_string_rotation(self):
for [s1, s2, expected] in self.data:
actual = string_rotation(s1, s2)
self.assertEqual(actual, expected)
if __name__ == "__main__":
unittest.main()
