열심히 썼는데 내용이 다 날아가서... 기운이 안 나지만 다시 써본다.. ㅋㅋ 리트코드 75 13일 차 Trie 2 문제, 비트 조작 1 문제를 풀어봤다. 이제 쉬운 미디엄은 거의 다 풀었는지 한 번에 풀리는 문제는 잘 없는 것 같다. 종종 에지 테스트 케이스에서 걸리는 경우가 있어서 서브밋 하기 전에 에지 케이스 생각해 보고 꼭 테스트해 보고 가는 습관을 들여야 하겠다.
208. Implement Trie (Prefix Tree)
Trie(트라이) 또는 prefix 트리는 문자열을 효율적으로 저장하고 가져오는 트리 자료구조다. 이 자료 구조는 자동완성이나 철자검사 등 다양한 응용이 있다. Trie 클래스를 다음과 같이 구현하라:
Trie() 생성자는 Trie 객체를 초기화한다. insert() 메서드는 인자로 받은 단어를 trie에 저장한다. search() 메서드는 인자로 받은 단어가 trie에 저장돼있으면 true를 리턴한다. startsWith() 메서드는 인자로 받은 prefix로 시작하는 단어가 존재한다면 true를 리턴한다.
A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
Trie() Initializes the trie object. void insert(String word) Inserts the string word into the trie. boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.
Trie도 트리 자료구조이기 때문에 속성으로 자식 노드들을 가진다. 우리가 자주 보는 이진트리와 다른 점이라면 자식 노드가 문자 종류만큼 많이 있을 수 있다는 것이다. 나는 범용적으로 구현하기 위해서 자식 노드들을 Map<Character, Trie> 형태로 구성했지만 문제에서 주어지는 단어를 소문자 알파벳으로 제한했기 때문에 Trie[] 배열로 구성하는 것도 가능하다. self 속성은 Trie에 입력한 단어의 끝을 알려주기 위해 사용한다. 예를 들어 child라는 단어를 입력하면 root -> 'c' -> 'h' -> 'i' -> 'l' -> 'd' (self = true) 마지막 문자 'd' 노드의 self 값은 true가 될 것이다.
class Trie {
private Map<Character, Trie> children = new HashMap<>();
private boolean self = false;
public Trie() {
}
public void insert(String word) {
Trie cur = this;
for(int i=0; i<word.length(); i++) {
char c = word.charAt(i);
Trie next = cur.children.getOrDefault(c, new Trie());
cur.children.put(c, next);
cur = next;
}
cur.self = true;
}
public boolean search(String word) {
Trie cur = this;
for(int i=0; i<word.length(); i++) {
char c = word.charAt(i);
if (!cur.children.containsKey(c)) {
return false;
}
cur = cur.children.get(c);
}
return cur.self;
}
public boolean startsWith(String prefix) {
Trie cur = this;
for(int i=0; i<prefix.length(); i++) {
char c = prefix.charAt(i);
if (!cur.children.containsKey(c)) {
return false;
}
cur = cur.children.get(c);
}
return true;
}
}각 메서드의 시간 복잡도를 살펴보면 인자로 받은 단어의 길이를 n이라고 했을 때, n 개의 노드를 순회/생성하기 때문에 O(n)이 된다. 그리고 공간복잡도는 입력되는 단어의 평균 길이를 n, 입력된 단어의 개수를 m이라고 하면 O(mn)이 된다.
1268. Search Suggestions System
위에서 구현한 Trie의 응용이다. 문자열 배열 products와 문자열 searchWord가 주어졌을 때, searchWord를 한 문자씩 타이핑했을 때 최대 3개의 product 이름을 제안하는 시스템을 설계하라. 제안된 product들은 searchWord과 공통 접두어를 가진다. 만약 제안된 product가 3개 이상이라면 접두어와 사전적으로 가까운 product를 리턴한다. 리턴 값은 searchWord 각 문자를 타이핑했을 때 제안된 product의 리스트의 리스트다.
You are given an array of strings products and a string searchWord.
Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.
Return a list of lists of the suggested products after each character of searchWord is typed.
위 문제에서 Trie를 구현할 때 자식 노드를 배열로 구현가능하다고 했었다. 그래서 이번에 구현한 Trie는 자식노드들을 배열로 선언했다. 제안된 product 리스트를 정렬해서 줘야 하는데, 배열을 순서대로 순회하면 그럴 필요가 없기 때문이다. 그리고 이번에는 insert() 메서드, getStartsWith() 메서드만 구현하였다.
class Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
Trie trie = new Trie();
for(String product : products) {
trie.insert(product);
}
List<List<String>> ret = new ArrayList<>();
for(int i=0; i<searchWord.length(); i++) {
String prefix = searchWord.substring(0, i+1);
List<String> prds = trie.getStartsWith(prefix);
ret.add(prds);
}
return ret;
}
class Trie {
Trie[] children = new Trie[26];
boolean self = false;
public Trie() {}
public void insert(String str) {
int len = str.length();
Trie cur = this;
for(int i=0; i<len; i++) {
char c = str.charAt(i);
int idx = c-'a';
if(cur.children[idx] == null) {
cur.children[idx] = new Trie();
}
cur = cur.children[idx];
}
cur.self = true;
}
public List<String> getStartsWith(String prefix) {
List<String> ret = new ArrayList<>();
Trie cur = this;
for(int i=0; i<prefix.length(); i++) {
int idx = prefix.charAt(i) - 'a';
if (cur.children[idx] == null) {
return ret;
}
cur = cur.children[idx];
}
StringBuilder sb = new StringBuilder(prefix);
startsWith(ret, sb, cur);
return ret;
}
private void startsWith(List<String> ret, StringBuilder sb, Trie cur) {
if (ret.size() == 3) {
return;
}
if (cur.self) {
ret.add(sb.toString());
}
for(int i=0; i<26; i++) {
Trie child = cur.children[i];
if (child != null) {
sb.append((char)(i + 'a'));
startsWith(ret, sb, child);
sb.deleteCharAt(sb.length()-1);
}
}
}
}
}시간 복잡도를 분석해 보자. Trie에 products 배열을 입력하는 작업이 있고, 그다음 searchWord의 prefix에 대해서 제안된 product 리스트를 찾아서 응답해 주는 작업이 있다. 첫 번째는 products의 문자열 길이를 전부 합한 크기를 M이라고 했을 때 O(M)이 된다. 두 번째 작업의 시간복잡도는 솔직히 계산이 쉽지 않다. 최악의 케이스를 생각해 보자. searchWord가 'abcde'이고 products가
['ae', 'af', 'ag',
'aba', 'abb', 'abd',
'abca', 'abcb', 'abcc',
'abcda', 'abcdb', 'abcdc',
'abcdea', 'abcdeb', 'abcdec'] 라면
각 prefix 길이별로 다른 suggest 결과를 리턴하는데, 결국 모든 products를 순회하는 결과가 된다. 그래서 두 번째의 시간 복잡도는 O(M)이 되고, 최종 시간 복잡도는 O(M)이 될 것이다. (아마도 🧐)
공간 복잡도는 products를 모두 저장하는데 중복되는 문자(노드)가 있을 것이라 노드의 개수만큼 필요할 것이라서 O(26m) = O(m)으로 볼 수 있다.
1318. Minimum Flips to Make a OR b Equal to c
양수 a, b, c가 있다. a OR b == c 가 되는 최소한의 비트 플립 횟수를 리턴하라. 플립 명령은 2진법으로 표현한 수의 단일 비트를 1에서 0으로 또는 0에서 1로 바꾼다.
Given 3 positives numbers a, b and c. Return the minimum flips required in some bits of a and b to make ( a OR b == c ). (bitwise OR operation). Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation.
a, b, c 세 숫자의 오른쪽 첫 번째 비트(least significant bit?)를 가져와서 비트 플립이 몇 번 필요한지 비교한다. 이 과정을 비트시프트를 하면서 a, b, c 모두 0이 될 때까지 반복한다. (abit | bit)가 cbit와 다를 때 비트 플립이 필요한데, cbit이 0일 때, cbit이 1일 때 비트 플립이 몇 번 필요한지 계산해 보자. cbit가 0일 때 a, b 모두 1이라면 비트 플립은 2회 필요하다. a 또는 b가 1이라면 비트 플립은 1회 필요하다. 그리고 cbit가 1인 경우는 OR 연산이기 때문에 둘 중 하나만 플립 하면 되니까 항상 1회 필요하다. 이것을 코드로 옮기면 된다.
class Solution {
public int minFlips(int a, int b, int c) {
int ret=0;
while(a > 0 || b > 0 || c > 0) {
int abit = a & 1;
int bbit = b & 1;
int cbit = c & 1;
if ((abit | bbit) != cbit) {
if (cbit == 0) {
if (abit == 1 && bbit == 1) {
ret += 2;
} else {
ret++;
}
} else {
ret++;
}
}
a = a >> 1;
b = b >> 1;
c = c >> 1;
}
return ret;
}
}int는 32비트니까 최대 32자리를 비교해야 하고 O(32) = O(1)이 시간복잡도가 된다. 그리고 공간 복잡도도 O(1)이다.
