개발조아

문제 링크 : https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 문제 등급은 높지만 어렵지 않은 문제이다. 핵심은 트라이 자료구조를 사용하는 것이다. 현재 문자에서 이어질 다음 문자를 다 저장했다가 사용해야므로 트리구조가 떠올랐고, 그중 다음 글자를 자식 노드로 저장하는 트라이가 떠올랐다. 우선 입력으로 들어온 단어를 모두 트라이로 구성하자. 이때 해당 글자에서 단어가 끝난다는 표시를 해주자. 다음은 루트 노드의 자식 글자에서 시작해서 재귀로 탐색하면..

문제 링크 : https://www.acmicpc.net/problem/9202 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net 트라이와 DFS를 사용해서 풀었다. 단어 사전에 단어가 최대 30만개 이므로 검색 시 오래 걸릴 것이다. 그래서 트라이로 단어 사전을 재구성하자. 트라이의 노드는 현재 글자, 자식, 단어의 끝 상태 3가지로 구성했다. 단어의 끝은 해당 글자로 끝나는 단어가 있다면 True로 설정했다. 그리고 boggle의 모든점에서 DFS를 실행하자. 이때 트라이도 함께 가져가자...

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 문제의 설명은 어렵지 않았다. 처음에는 word에 ?를 하나씩 붙여서 가능한 경우를 다 만들고 그것을 키로하고 값은 개수로 하는 딕셔너리로 만들었었다. 그리고 쿼리문을 키로해서 딕셔너리를 확인했다. word의 길이는 최대 10000자이고, 모든 가사의 길이의 합이 1백만자 이하 이므로 되지 않을까 했다. 근데 문자를 이어붙이는 과정에서 슬라이싱이 많이 들어가서 효율성 테스트에서 틀리지 않았나 싶다. 그래서 해설을 봐보니 트라이 자료구조를 사용해야한다고 한다. 문자열을 트리 구조로 저장해서 단순 비교해서 검색하는 경우 훨씬 빠르다..