19585번 - 전설
안녕하세요, 이 문제를 풀다가 궁금증이 생겼습니다.
제출번호 104324780 과 104304230은 팀 이름이 존재하는지 찾기 위해서 단순히 트라이를 썼냐, 해시셋을 썼냐의 차이입니다.
여기서 문자열이 set에 포함되는지 찾기 위해서 문자열을 슬라이싱하는 과정에서 O(n)의 시간복잡도가 쓰이는 것으로 알고 있습니다.
최종적으로 봤을 때 두 코드 모두 시간 복잡도가 같아보이는데 왜 트라이를 구현했을 때 시간초과가 날까요...?
고수님분들의 답변 부탁드립니다.
댓글을 작성하려면 로그인해야 합니다.
kkigon 7달 전
안녕하세요, 이 문제를 풀다가 궁금증이 생겼습니다.
제출번호 104324780 과 104304230은 팀 이름이 존재하는지 찾기 위해서 단순히 트라이를 썼냐, 해시셋을 썼냐의 차이입니다.
여기서 문자열이 set에 포함되는지 찾기 위해서 문자열을 슬라이싱하는 과정에서 O(n)의 시간복잡도가 쓰이는 것으로 알고 있습니다.
최종적으로 봤을 때 두 코드 모두 시간 복잡도가 같아보이는데 왜 트라이를 구현했을 때 시간초과가 날까요...?
고수님분들의 답변 부탁드립니다.