728x90
1. 오늘의 문제
오늘 문제는 그리 어려워보이지 않았다.
처음에는 말이다
그런데 효율성 검사 무엇??
2번을 통과 못해서 결국 인공지능의 도움을 받았다.
더보기
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.
가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.
가사 단어 제한사항
- words의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.
- 각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
- 전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.
- 가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공됩니다.
- 각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
검색 키워드 제한사항
- queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.
- 각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
- 전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.
- 검색 키워드는 중복될 수도 있습니다.
- 각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
- 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.
2. 원리
이 문제의 해법은 두 가지가 있다.
- trie 이용. hashmap의 탐색 속도가 더 빠르다는 것을 이용해 trie class를 만든다. trie는 각 단어마다 한 단계씩 깊어지는 해시맵 구조를 가진다. 파이썬이면 딕셔너리 구조, 만약 자바스크립트라면 객체의 형태가 된다. 예를들어 'cat'을 trie구조로 만들면 trie = {'c': {'a': {'t': {'val': 1}}}}와 같은 구조가 된다. 마치 러시아 인형같은 구조다.
- 이진탐색 이용. bisect라는 모듈을 이용해 각 단어 범위를 구한다. 예를들면 fro???가 있다면 fro에서 부터 frozzz까지 범위에 속하는단어의 개수를 센다. 그러기 위해서는 단어를 길이별로 정렬해야 한다.
하나씩 살펴보자.
3. trie 이용
class TrieNode:
def __init__(self):
self.children = {}
self.length_count = {} # 각 길이별 단어 개수를 저장
self.is_terminal = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
length = len(word)
# 모든 길이에 대해 카운트 증가
for level in range(len(word) + 1):
if length in node.length_count:
node.length_count[length] += 1
else:
node.length_count[length] = 1
if level == len(word):
break
char = word[level]
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_terminal = True
def count_match(self, query):
node = self.root
length = len(query)
# 와일드카드가 접두사인 경우
if query[0] == '?':
return node.length_count.get(length, 0)
# 일반 문자로 시작하는 경우
for char in query:
if char == '?':
return node.length_count.get(length, 0)
if char not in node.children:
return 0
node = node.children[char]
return node.length_count.get(length, 0)
def solution(words, queries):
# 정방향, 역방향 Trie 생성
forward_trie = Trie()
reverse_trie = Trie()
# 단어 삽입
for word in words:
forward_trie.insert(word)
reverse_trie.insert(word[::-1]) # 역방향 삽입
answer = []
# 각 쿼리 처리
for query in queries:
if query[0] == '?': # 접두사가 와일드카드인 경우
# 쿼리를 뒤집어서 역방향 Trie에서 검색
result = reverse_trie.count_match(query[::-1])
else: # 접미사가 와일드카드인 경우
result = forward_trie.count_match(query)
answer.append(result)
return answer
4. bisect 이용
def solution(words, queries):
from bisect import bisect_left, bisect_right
# 단어 목록을 길이별로 분류
words_by_length = [[] for _ in range(10001)]
reversed_words_by_length = [[] for _ in range(10001)] # 역순 저장용
for word in words:
words_by_length[len(word)].append(word)
reversed_words_by_length[len(word)].append(word[::-1]) # 역순으로 저장
# 각 길이에 대해 정렬
for i in range(10001):
words_by_length[i].sort()
reversed_words_by_length[i].sort()
def count_range(word_list, left, right):
return bisect_right(word_list, right) - bisect_left(word_list, left)
answer = []
for query in queries:
if not query:
answer.append(0)
continue
if query[0] == '?': # 쿼리가 '?'로 시작하는 경우
query = query[::-1] # 쿼리를 뒤집음
word_list = reversed_words_by_length[len(query)]
prefix = query.replace('?', '')
left = prefix
right = prefix + 'z' * query.count('?')
else: # 쿼리가 '?'로 끝나는 경우
word_list = words_by_length[len(query)]
prefix = query.replace('?', '')
left = prefix
right = prefix + 'z' * query.count('?')
count = count_range(word_list, left, right)
answer.append(count)
return answer
5. 느낀점
세상은 역시나 넓고 코딩 잘하는 놈들은 너무 많다.
그래도 오늘은 tire이라는 자료 구조와 bisect라는 라이브러리를 알게 된 것으로 만족한다.
원래는 자바 스크립트 실력 키우려고 과감하게 nodejs로 신청했는데, 결국은 파이썬으로 문제를 풀고 말았다.
다음에는 꼭 자바로 풀어보고 싶.....은 마음 뿐이다.
728x90
