[2020 카카오 기출] 가사 검색(JAVA)

문제: https://programmers.co.kr/learn/courses/30/lessons/60060

---

참고 링크: https://shjz.tistory.com/99

shjz님의 블로그 글을 참고해서 해결했습니다.

 

중요한 점은 3가지 입니다.

 

1. 트라이 사용 문제

2. 정방향 트라이와 역방향 트라이를 사용

3. 문자열 길이만큼 트라이배열을 만들어서 사용

 

---

1. 트라이 사용 문제

 

각 문자열에 대한 판단을 O(M) (M: 문자열의 길이)에 끝내기 위해 트라이를 사용합니다.

---

2. 정방향 트라이와 역방향 트라이를 사용

 

'?'(와일드 카드 식별자)가 중간에 나오지 않는다는 뜻은 

'?'가 나온 시점에는 나머지 탐색에 대한 처리가 상수 시간에 끝나야 합니다. 

그렇게 처리하지 않고 26(알파벳 크기)^(남은 문자열의 길이) 만큼 루프를 돌면 시간초과가 납니다.

 

물음표를 상수 시간에 처리하려면 물음표는 접미사 형태로만 나와야 합니다.

왜냐면 ?????abc 같은 문자열을 접두사에서 물음표 처리를 하려면 어쩔 수 없이 알파벳 크기만큼 루프를 돌아야 합니다.

 

그러므로 주어진 문자열을 그대로 저장하고 있는 trie와 거꾸로 저장하고 있는 reverse_trie 를 만듭니다.

 

또한, 물음표가 나온 시점에 남은 문자열에 대한 판단을 상수시간에 처리하기 위해 

동일한 길이의 문자열만 따로 모아서 트라이에 넣습니다. 이게 무슨 말인지는 아래 3번에서 설명하겠습니다.

---

3. 문자열 길이만큼 트라이배열을 만들어서 사용

 

아래 코드는 문자열의 길이가 0~10,000 까지인 각 문자열들을 저장하고 있는 트라이를 의미합니다.

Trie[] root = new Trie[100001];
Trie[] reverseRoot = new Trie[100001];

 

root[6]: 문자열의 길이가 6인 문자열만 저장

root[10]: 문자열의 길이가 10인 문자열만 저장

 

이게 필요한 이유는 쿼리로 주어진 문자열이 아래와 같을 때 두 문자열을 어떻게 구분해야 할까요?

//Query.1
boj????????

//Query.2
boj???????????????????

물음표가 나온 시점에 탐색이 끝나야 하지만 길이 정보를 알 수 없으므로 상수시간에 탐색을 끝낼 수 없습니다.

그러므로 같은 길이의 문자열만 저장해놓고, 쿼리가 들어올 때도 문자열 길이에 맞는 트라이가 처리하도록

해줘야 합니다.

---

코드: https://github.com/cotchan/algorithm/blob/main/java/PROGRAMMERS/PG60060.java