바킹독님이 트라이 강의를 올려서 다시 공부했습니다. 트라이 문제를 좀 풀어본 적이 있어서 복습일 줄 알았는데, 트라이 구현 방식이 달라서 좀 새로웠네요. 이 방법을 알았다면 현대모비스 알고리즘 경진대회에 나온 트라이 쓰는 2문제에서 더 높은 점수를 받을 수 있지 않았을까? 싶기도 합니다.
기존에 트라이를 블로그를 통해 공부했을 때, 다들 구현 방법으로 Trie class를 만들어 사용하는 방법을 제시하더라고요. 그리고 Trie내의 자식 노드를 구현을 1) Map<node, Trie>으로 하는 방법, 2) 적당한 크기의 Trie배열을 선언하는 방법으로 나눌 수 있었습니다.
위 강의에서는 처음부터 2차원 배열을 크게 선언한 다음 사용하라고 했는데, 처음 보니까 조금 생소하기도 하고 비효율적이다는 느낌(되게 안쓰는 칸이 많아요)을 받았는데, 문제를 좀 풀어보니까 더 빠르고, 평소에 쓰던 array 쓰는 거라 편합니다. 앞으로도 이렇게 풀 거 같아요. 다만 몇몇 문제에서는 메모리 문제가 발생할 수 있는데, 이럴 때만 class를 이용한 Map 풀이를 하면 될 듯합니다.
문제들 (링크)
11425번: 문자열 집합, 14426번:접두사 찾기
기본
5052번: 전화번호 목록
트라이에 순서대로 넣으면서 1) 기존 문자열에 완전히 포함되거나, 2) 기존 문자열을 완전히 포함하는지 확인하면 됩니다.
7432번: 디스크 트리
이차원 배열로 풀려면 각 노드를 적당한 형태의 숫자로 바꿔야 하는데, 본 문제에서는 하나의 노드가 8글자 이하의 String이기에 Trie class를 만들어 풀었습니다.
14725번: 개미굴
디스크 트리랑 비슷합니다.
16934번: 게임 닉네임
닉네임을 넣으면서, 각 닉네임별로 알파벳을 트라이에 삽입합니다. 만약 만나지 않은 노드에 도달했으면, 해당 노드의 알파벳까지만 치면 구분이 가능하기에 별칭을 거기까지만 해서 등록을 합니다. 마지막 노드에 도달했는데, 이미 해당 노드를 마지막으로 하는 경우(=같은 닉네임이 이미 등록된 경우) 그 횟수를 기록해두어(마지막임을 기록하는 배열을 boolean이 아니라 int로 하면 됩니다.) 등장횟수 + 1만큼 뒤에 붙여주어 별칭으로 만들어줍니다.
9202번: Boggle
처음에는 각 board별로 trie에 넣고, 문자열을 찾는건가 했는데 그 반대입니다. w개의 문자를 다 넣어준 후, 각 board별로 최대 길이가 8인, 길이가 8이하인 단어를 만들어 속하는지 확인해주면 됩니다. 보드에서 단어를 만드는거다보니, dfs 및 백트래킹을 활용합니다.
시간 복잡도가 어떻게 되는지 잘 모르겠네요. 그래서 (아마 가장 많은 탐색을 하지 않을까 싶은) 첨부파일과 같은 테스트케이스를 만들어서 dfs 함수의 호출 횟수를 세봤는데, 900만번도 안되더라고요. 10초 제한도 널널합니다.
그리고 dfs에서 문자를 concat하기보다 (단어 사전에 있는 단어를 완성했을 때 도달하는 숫자)와 (단어 사전 리스트의 인덱스)를 대응시켜 문자를 $ O(1) $에 찾아줍시다. 근데 보니까 그렇게 안해도 문제는 풀리는 듯합니다.
되게 재미있고, 추천할만한 문제라 느껴집니다.
16906번: 욱제어
한 단어가 다른 단어의 접두어가 되지 않도록 해야 합니다.
생각해보면 짧은 단어를 먼저 넣어야한다는 사실을 관찰할 수 있습니다. 예를 들어, 만약 00000이 들어가있는데, 길이가 3인 문자열 4개를 넣는 상황을 생각해보면 쉽지가 않습니다. 첫번째 0을 이미 방문했을테니까 100같은 문자열을 넣었다고 하면, 다음 문자열은 어디에 넣을까요? 지금 이런 상황에서야 직관적으로 101 넣으면 된다는 걸 알지만, 기존 트라이 구현에서는 첫 번째 0이든 1이든 방문했다고 나타나있을텐데 말입니다. 근데 다른 분들 코드를 보니까 정렬 안하신 분들도 있는 거 같은데, 잘 모르겠네요ㅎㅎ
그래서, 단어를 길이의 오름차순대로 넣도록 합니다. 넣을 때는 '최대한 왼쪽'에 쑤셔넣도록 합니다. 예를 들어, 길이가 2인 문자열을 4개 넣는다고 하면, 00, 01, 10, 11 순으로 넣으면 됩니다. 그래도 안 들어가면 -1을 출력하면 됩니다.
위 문제보다더 더 재미있게 풀었는데, 코테 스타일 문제는 아니긴합니다.
5670번: 휴대폰 자판
메모리 제한이 빡빡해서 이차원 배열 풀이로는 메모리 초과가 뜨네요. 최적화를 못한걸 수도 있는데, 일단은 Trie class 만들어서 하면 되니까 넘어가도록 합니다.
처음에는 무조건 눌러야 하고('p'만 있다고 바로 p가 완성되지는 않으니까요), 이후에는 해당 노드에 방문한 횟수가 1보다 크거나 현재 노드에서 끝나는 경우("abc"와 "ab"가 있고, "abc"를 검색하는 경우: 일단 a를 누르고 b가 자동완성되면 c를 눌러야한다.)에는 그 다음 글자를 눌러줘야 합니다.
5446번: 용량 부족
"...*'로 지우면 안되는 글자가 있다면, 해당 글자의 노드마다 지우면 안된다는 표시를 해둡니다.
이후 지우는데, 만약 지워도 되는 노드를 만났다면 '...(노드)*' 명령어로 지워버립니다.
지우면 안 되는 노드이지만 지워야하는 파일명의 마지막 노드라면 '...(노드)' 명령어로 지우고, 다음 노드를 살펴봅니다.
지우면 안 되는 노드이면 그냥 다음 노드로 넘어갔습니다.
트리에서 각 노드 방문을 한 번씩 하는 방식으로 구현했어서 실제로 지우진 않았습니다.