ababc1005   9달 전

기본적으로

색상과 이름 모두 트라이로 저장, 

트라이 구조는 vector로 구현 (없을 때마다 추가로 push_back)

해서 구현하니까 시간초과가 나더라구요.


그래서 2가지 곁다리 최적화를 해서 결국 AC를 받기는 했는데 개인적으로 좀 구차한 방법이라 문제 의도가 이게 맞나...? 싶네요

1. string을 잘라가며(substr 등 사용시 string 복사에 시간 소요) 다음 노드로 전달하지 않고 main함수에 저장된 주소값을 불러오고, index를 +1 해가며 다음 노드로 전달 -> 생각보다 여기서 절약되는 시간이 매우 크더군요.. 이것도 시간초과가 나서 2번도 넣었습니다.

2. trie에 저장된 max길이를 기억해 두었다가 그걸 넘으면 애초에 검색을 시도도 안함. -> 팀네임 길이가 2000자, 각 색상/닉네임 길이가 1000자라 쓸데없는 연산이 꽤 있거나 이를 노린 TC가 있을 것 같아 짧은 조건문 넣어보니까 바로 통과가 되었습니다.  


이런 구차한 방법 안 사용하고 풀 수 있도록 시도해본 방법에는,

1. vector 대신 map을 사용한 trie -> 깔끔하게 메모리 초과

2. unordered_set<string>로 N(1)에 검색 -> 메모리 초과

이 두 가지가 있습니다.

제 짧은 지식으로는 unordered_set은 기본적으로 hash와 비슷한 형태라고 들었는데 왜 메모리 초과가 나는지는 잘 모르겠네요 ㅠㅠ 

이 외에 더 깔끔한 풀이가 뭐가 있는지, 혹은 예상되는 기존 방법들이 실패했던 이유가 뭐가 있을지 가르쳐주시거나

각자 사용했던 방법 공유해주시면 성장에 큰 도움이 될 것 같습니다!


이것저것 시도하느라 정답코드는 매우 지저분하긴 한데.. 일단 이것도 업로드 합니다:)

djs100201   9달 전

저는 trie일절 안쓰고 해싱 + 해싱 했습니다.

dustkd1004   9달 전

일단 저는 color, name 두개 모두 map을 활용한 trie로 구현했습니다.

child 구현 방식은 포인터배열, STL map 활용 2가지로 알고 있습니다.

포인터배열은 자식에 빨리 접근할 수 있지만 메모리 사용이 많고

map은 비교적 메모리를 적게 사용하는 반면 탐색효율이 상대적으로 안좋아지는 것이죠.

map을 활용한 trie 구현이 왜 메모리초과가 발생하는 지 한번 다시 확인해보시는 것도 좋아보이네요.


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