Hash function1 [자바] 백준 14426 - 접두사 찾기 (boj java) 문제 : boj14426 정해는 대놓고 Trie 쓰라고 낸 거 같은 문제이다. 하지만 N, M, 문자열의 길이가 애매하게 적고 메모리가 상당히 많다. 그래서 밑져야 본전이니 메모리를 많-이 써서 한번 해보고 통과하면 통과되는거고, 안되면 Trie 쓰려고 했는데 이렇게 썼단 이유는 됬다는 그런 얘기이다. 일단 단순히 브루트포스로 풀려고 하면 O(500xNxM) 이므로 불가하다. 하지만 메모리를 더 써서, 미리 N개에 대해 접두사 HashSet을 만들어두면 어떨까? 이 경우 String이라 hash function에 다소 부하는 걸리겠지만, 대강 O(1)이라고 치면 O(500N + M) 으로 가능하다. hash function의 부하를 생각해도 대강 통과는 될 것 같아서 해봤다. 추가로 약간이라도 hash .. 2022. 5. 16. 이전 1 다음
