문제
words | queries | result |
["frodo", "front", "frost", "frozen", "frame", "kakao"] | ["fro??", "????o", "fr???", "fro???", "pro?"] | [3, 2, 4, 1, 0] |
•
query에 일치하는 words의 갯수를 각각 담아 반환하면 되는 문제.
•
물음표는 와일드 카드이고 어떤 문자가 들어와도 일치한다.
풀이 과정
•
처음에는 단순한 구현 문제인줄 알고 풀었다.
class Solution {
public int[] solution(String[] words, String[] queries) {
int[] answer = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int tmp = 0;
String token = queries[i];
Iterator it = Arrays.stream(words).iterator();
while (it.hasNext()) {
String word = (String) it.next();
if (word.length() != token.length()){
continue;
}
for (int p = 0; p < word.length(); p++) {
if (token.charAt(p) != '?' && token.charAt(p) != word.charAt(p)) {
tmp --;
break;
}
}
tmp++;
}
answer[i] = tmp;
}
return answer;
}
}
Java
복사
•
일단 문제 구조 상 HashMap을 사용해도 최대 O(N^2)의 시간 복잡도가 나오기 때문에 효율성이 문제 겠구나 생각했었다.
•
단어의 길이부터 비교하는 등 elary continue를 하면서 나름대로 효율성을 신경 썻다고 생각했지만 효율성에서 실패했다.
테스트 1 〉 통과 (0.83ms, 73.3MB)
테스트 2 〉 통과 (1.34ms, 73.8MB)
테스트 3 〉 통과 (0.57ms, 73.6MB)
테스트 4 〉 통과 (0.50ms, 76.4MB)
테스트 5 〉 통과 (0.52ms, 73.1MB)
테스트 6 〉 통과 (0.73ms, 74.6MB)
테스트 7 〉 통과 (8.53ms, 78.4MB)
테스트 8 〉 통과 (9.26ms, 80.5MB)
테스트 9 〉 통과 (10.68ms, 83MB)
테스트 10 〉 통과 (7.93ms, 77.6MB)
테스트 11 〉 통과 (7.96ms, 81MB)
테스트 12 〉 통과 (12.40ms, 68.6MB)
테스트 13 〉 통과 (39.12ms, 83.5MB)
테스트 14 〉 통과 (37.13ms, 93.4MB)
테스트 15 〉 통과 (28.08ms, 84.2MB)
테스트 16 〉 통과 (31.33ms, 78.4MB)
테스트 17 〉 통과 (35.82ms, 76.9MB)
테스트 18 〉 통과 (32.81ms, 91.8MB)
효율성 테스트
테스트 1 〉 실패 (시간 초과)
테스트 2 〉 실패 (시간 초과)
테스트 3 〉 실패 (시간 초과)
테스트 4 〉 통과 (38.94ms, 59.7MB)
테스트 5 〉 통과 (62.27ms, 60.3MB)
Java
복사
트라이 자료구조
•
트라이는 트리의 일종으로 탐색에 효과적이다.
•
동적으로 저장되는 문자열을 키로 하는 경우가 많다.
트라이의 삽입 과정을 사진을 보며 이해하면 빠르다.
1.
Hello 삽입
2.
Hi 삽입
•
‘H’ 노드가 이미 있기 때문에 I를 H의 자식 노드 중에서 검색한다.
3.
반복
•
빨간색으로 된 노드는 리프노드 즉, 해당 노드에서 끝나는 문자열이 저장되었다는 뜻이다.
구현
Java
복사