trie2 [Python] Trie 자료구조 Trie(트라이) 자료구조는 문자열 집합에서 키를 효율적으로 저장하고 조회하는데 사용된다. 스펠 체커나 자동완성 기능에서 사용된다. 파이썬에서는 딕셔너리 자료구조를 이용해 쉽게 구현할 수 있다. insert (단어 삽입) 단어의 키(문자)가 커서에 존재하지 않는 경우 해당 키로 딕셔너리를 생성하고, 커서 위치를 업데이트 해준다. 단어 삽입이 완료되면 * 키를 생성해서 끝임을 표기한다. search (단어 조회) 단어의 키(문자)가 커서에 존재하지 않는 경우 False를 반환하고, 커서 위치를 업데이트 해준다. 단어 순회가 완료되었을 때 * 키가 커서에 있을 경우 True를 반환하고 없을 경우 False를 반환한다. startswith (접두어 조회) 단어의 키(문자)가 커서에 존재하지 않는 경우 Fals.. 2021. 10. 10. [Python] 전화번호 목록 https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr Point 해쉬를 이용한 문제로, 트라이(Trie) 자료구조를 응용해서 풀어보기 좋은 문제이다. 실제로 많은 분들이 리스트와 반복문을 이용해서 풀고 있는데, 만약 문제의 제약조건이 타이트했다면 해결하기 어려울 것이다. Tip 정렬을 하지 않는 것이, 최악 테스트케이스에서 수행 시간이 더 빠르다. 따라서 prefix+a 문자열이 이미 트라이에 있을 때, pre.. 2021. 9. 25. 이전 1 다음 728x90 반응형