[트라이]
트라이(Trie)는 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는데 사용되는 정렬된 트리 자료구조이다. 다진 트리의 형태를 띤다. 문자열 길이 만큼만 탐색하면 원하는 결과를 찾을 수 있다.
(1)트라이 구현-하, 트라이
트라이의 insert, search, startWith 메소드를 구현하라.
https://leetcode.com/problems/implement-trie-prefix-tree/
[팁!!!]
딕셔너리를 이용해서 하나씩 넣고 그 노드로 이동.
[펠린드롬 페어] (난이도 극상), 트라이*** 아직 이해 x
단어 리스트에서 words[i] + words[j]가 팰린드롬이 되는 모든 인덱스 조헙(i, j)를 구하라(팰린드롬에 대한 정의는 138페이지를 참조하라).
https://leetcode.com/problems/palindrome-pairs/
[팁!!!]
브루트 포스로 풀었을 경우 시간 초과로 테스트 케이스를 통과 할 수 없다.
[@staticmethod 데코레이터]
class CLASS:
def a(self):
pass
@staticmethod
def b():
pass
>>> type(CLASS.a), type(CLASS.b)
(<class 'function'>, <class 'function'>)
#클래스를 생성하지 않고 바깥에서 직접 호출했을 때 타입은 이처럼 둘다 함수가 된다.
>>> cls = CLASS()
>>> type(cls.a), type(cls.b)
(<class 'method'>, <class 'function'>)
#그러나 클래스를 생성한 후에 함수에 대한 타입을 보면, 이렇게 a는 메소드가 된다. 하지만,
#staticmethod로 선언한 것은 독립된 함수의 의미를 가진다. 사실상 클래스 밖에 별도로 선언한 것과 같다.
#이렇게 하면 자유롭게 클래스 인스턴스에 접근 하는 것이 제한된다.