Trie3 [Leetcode] 1032. Stream of Characters 문제 : https://leetcode.com/problems/stream-of-characters/ 문자열 리스트 words가 입력으로 주어지고 추가될 알파벳 소문자가 한 글자씩 입력으로 들어온다. 추가될 알파벳들은 초기 빈문자열에서 뒤에 하나씩 추가된다. 알파벳이 하나씩 추가되어 만들어진 문자열의 접미사가 words 배열에 존재하는지 판단해라. 트라이(Trie)를 만들어야 한다. words 문자열들을 뒤에서 부터 탐색하면서 트라이를 만들어간다. 예를 들어, words = ["abc", "bc", "dc"] 인 경우 [그림 1]과 같은 트라이가 만들어진다. 1번 노드가 트라이의 헤드 노드이며 빨간색 체크한 부분이 문자열의 끝을 의미한다. 알파벳들을 하나씩 받으며 만들어진 문자열을 마찬가지로 뒤에서부터 .. 2021. 12. 4. [programmers][2020카카오공채] 가사 검색 문제 : https://programmers.co.kr/learn/courses/30/lessons/60060 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다. 단어들이 주어지고 접미사, 접두사를 제공하며 단어들의 개수를 묻는다. -> 트라이! 접두사에 대한 질문은 문자열의 앞에서부터 탐색하니까 일반적으로 풀 수 있는데 접미사는 뒤에서부터 탐색해야 하므로 문자들을 역순으로 만든 후 트라이를 하나 더 만든다. (접미사, 접두사를 위해 각자 1개씩 2개의 트라이 생성) 검색 키워드가 문자로 시작하는 경우(?로 끝나는 경우) 접두사를 위해 만든 트라이를 이용하여 탐색하고, 검색 키워드가 ? 으로 시작하는 경우 해당 키워.. 2020. 5. 12. [Kickstart][2020][Round A] 4. Bundling 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d3ff3 Pip는 N개의 문자열을 가지고 있다. 문자열들은 모두 대문자로만 이루어진다. Pip는 이 문자열들을 그룹화 시키려고 한다. 이 때, 각 그룹은 정확히 K개의 문자열들로 이루어진다. 각 그룹의 점수는 그룹에 속한 문자열들의 공통 prefix 길이다. 만들 수 있는 그룹들의 점수의 합의 최대값은 얼마인가. 문자열 배열, 공통된 Prefix.. 트라이를 써야될 것 같은 느낌이 든다. 일단 N개의 문자열들로 Trie를 만든다. 그룹들의 최대값을 만드려면 어떻게 해야하는지 먼저 고민해보자. 최대값을 만드려면 prefix가 커야한다. 즉, 트.. 2020. 3. 26. 이전 1 다음
