저도 특별히 시간 복잡도가 문제가 되지 않는다면 set이나 map으로 방문 처리를 합니다.
그 시간이 문제가 된다면 보다 최적화할 수 있는 방법이 몇 가지 있습니다. 문자열 각각이 독립적인 경우에는 각 문자열에 순서대로 번호를 매겨놓고 (이 부분은 map으로 하면 됩니다) 이후로는 이 번호들을 가지고 방문 체크를 할 수도 있고, 해시를 사용해서 문자열끼리 비교하는 시간을 단축시킬 수도 있습니다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호
jh0956 4년 전
탐색 문제들 풀다보면
배열로 표현가능한 정수들은 배열을 통해서 쉽게 방문 확인이 가능한데
string의 경우는 어떤 방법으로 확인하시는지 궁금합니다.
저는 지식이 부족하여서.. set을 이용해서 지금껏 문제를 해결해왔습니다.
방문 확인하고 싶은 스트링을 insert -> 직전의 size와 현재의 size를 비교해서 다르면 방문하지않은 스트링으로
평균적으로 logN 정도의 시간이면 나쁘지않은 속도가 아닐까하고.. 부끄럽네요ㅠㅠ
어떤 좋은 방법들이 있는지 질문드리고 싶습니다.
혹시 트라이 자료구조를 익혀두는게 좋을지도 질문드리고 싶습니다.