BOJ 17050

https://www.acmicpc.net/problem/17050

 

 

코드

http://boj.kr/70deeac7b2b2446487665d909f26a5a0

 

Croatian Open Competition in Informatics 2018/2019 Contest #5

 

난이도 : P4

 

Elapse Time : 25min

 

문제를 읽고 트라이를 쓰면 편할 것 같다는 느낌이 들었다. '?'가 처리 가능한지와 '?'를 처리할 때 시간 복잡도가 커지지 않는지가 관건이었다. 트라이에 '?'가 포함된 단어를 삽입할 때와 트라이에서 '?'가 포함된 단어와 일치할 수 있는 단어의 개수를 세어 답에 더해줄 때 2가지를 처리해야 했다. '?'가 포함된 단어를 삽입하는 것은 트라이를 만들 때 인덱스 하나를 추가해 주면 되기 때문에 문제가 없지만 '?'가 포함된 단어와 일치할 수 있는 단어들을 검색할 때가 문제였다. '?' 대신 'a'~'z', '?'를 모두 봐주면 시간복잡도가 최악의 경우 $O(27^MN)$이 되므로 불가능하다. 여기서 조금 더 관찰을 해보니 '?'는 'a'~'z'와 '?' 모두를 봐주면 되는데 이 값을 저장하는 인덱스 하나를 더 만들면 될 수도 있을 것 같았다. 'a'~'z'를 0~25에 대응시키고 '?'를 26, '?' 검색용 노드를 27에 대응시켜 트라이를 만들어보기로 했다. 단어를 추가할 때 각 문자에 대응되는 노드 1개와 27번 노드에 추가를 해주어야 하므로 삽입할 때 시간복잡도 $O(2^M)$, 검색의 경우 '?'는 27번 노드만 봐주면 되고 'a'~'z'는 각 문자에 대응되는 노드와 26번 노드를 봐주어야 하므로 시간복잡도 $O(2^M)$이다. 총 시간복잡도기 $O(2^MN)$이므로 충분히 시간 안에 돌아갈 것이라고 생각했고 맞았다.

 

내 풀이가 정해일 것이라고 생각했으나 아니었다. kwoncycle님의 코드를 참고해 정해를 알아보았다.

'?'가 아닌 위치에 1, '?'인 위치에 0을 대응시켜 하나의 정수로 만들 수 있다. 이를 인덱스로 하는 string 이중 배열들을 만들고 모든 $(i,j)$에 대해 $map$을 활용해 일치할 수 있는 경우의 수를 구해 더해주면 된다.