[알고리즘] 문자열 탐색용 자료구조 Trie

기본형 class Trie { data class TrieNode(var isEndOfWord : Boolean, val children : MutableMap) val root = TrieNode(false, mutableMapOf()) fun insert(word : String) { var currentNode = root word.forEach{ char -> val child = currentNode.children[char] ?: TrieNode(false, mutableMapOf()) currentNode.children[char] = child currentNode = child } currentNode.isEndOfWord = true } fun search(word : String) :..

→2020. 9. 8. 14:33

solved

[알고리즘 문제/2020 KAKAO BLIND RECRUITMENT] 가사 검색

해결 코드 insert할 때 입력된 현재 노드에서 도착할 수 있는 단어를 남은 글자수 별로 저장 (countEndOfWordPerDepth) 예를 들면, "frodo" 단어를 추가하면 root에 countEndOfWordPerDepth[5]++ root.children['f'].countEndOfWordPerDepth[4]++ root.children['f'].children['r'].countEndOfWordPerDepth[3]++ 과 같이 저장해서 '?'가 나오기 전까지의 노드를 찾고 해당 노드에서 '?'의 갯수 즉 depth에 저장된 단어 수를 return하면 빠르게 정답을 도출할 수 있다. 2차 해결코드에서 하위노드를 돌며 정답을 계산하는 단계를 줄일 수 있음 import kotlin.test.*..

→2020. 9. 8. 09:54

solved

[알고리즘 문제/2020 KAKAO BLIND RECRUITMENT] 괄호 변환

import kotlin.test.* class Solution { fun solution(s : String) : String { return tailrecChangeBalancedBracketToRightBracket("", s, "") } private tailrec fun tailrecChangeBalancedBracketToRightBracket(prev : String, s : String, next : String) : String { return when { s == "" -> prev + "" + next s.length == 2 -> prev + "()" + next else -> { val u = getFirstBalancedMinimum(s) val v = s.replaceFirst..

→2020. 9. 3. 10:05

[알고리즘] 문자열 탐색용 자료구조 Trie

[알고리즘 문제/2020 KAKAO BLIND RECRUITMENT] 가사 검색

[알고리즘 문제/2020 KAKAO BLIND RECRUITMENT] 괄호 변환

티스토리툴바