Nyan101   5년 전

아호-코라식을 해결했고, 메모리 문제를 해결하기 위해 map(unordered_map)을 사용했습니다. 노드 개수는 최대 5000x5000 = 2500만이라고 가정했습니다.

1) 전체를 map으로 한 경우(28020252번 제출)

: 시간 초과를 받습니다

2) 시간 초과를 막기 위해 각 노드마다 map을 별도로 만든 경우(28022120번 제출)

: 메모리 초과를 받습니다.

3) 1),2)의 절충안으로 map을 버킷화한 경우(28025061, 28024853번 제출)

: 시간 초과, 혹은 버킷 크기에 따라 메모리 초과를 받습니다

4) 혹여나 하고, 2)를 구현하되, 노드의 최대 개수를 450만이라고 가정해 제출한 경우(28025275번 제출)

: 정답 판정을 받습니다.

문제점1) 데이터가 약합니다. 노드의 최대 개수는 이론상 5000x5000 = 2500만이 되어야 합니다.

문제점2) 난이도 기준상 아호-코라식 구현이 의도된 정해인 것으로 보이는데, 데이터를 강화하면 메모리/시간 제한이 부족해집니다.

데이터를 추가하고 시간 제한을 충분히 늘리는 게 맞을 듯 합니다.

startlink   5년 전

데이터 첨부해주세요.

댓글을 작성하려면 로그인해야 합니다.