jeha0714   2년 전

연결리스트 탐색 시간복잡도는 O(n) 아닌가요?

해당 문제를 위해 기존에 생성되어있던 역 N개, 고유번호 i를 찾기 위해 공사하는 횟수인 M을 곱하는

O( N * M )이 해당 문제의 시간복잡도인것 같은데 시간초과가 뜨네요...

연결리스트 탐색에서 순차접근외에 다른 탐색방법이 있을까요?

neogate   2년 전

이 문제를 보게되면 각 역들이 연결되어있지만 실제로 필요한 정보는 각 역마다 앞의 역과 이전 역의 고유번호밖에 없습니다.

따라서 각 고유번호마다 앞의 역과 이전역의 고유번호만 저장해주고 쿼리마다 알맞게 조절해주시면 됩니다.

추가로 역의 개수가 N이긴 하지만 여기서는 고유번호를 사용한다는 것을 생각하면 

1000000 * 1500000 = 1.5 * 10^12 이므로 

각 쿼리마다 O(고유번호 개수)가 아닌 O(1)의 복잡도로 접근하셔야합니다.

jeha0714   2년 전

감사합니다 덕분에 해결했습니다!

yhsooi   1년 전

저도 똑같이 시간초과가 뜨는데 어떻게 해결하셨는지 자세히 설명해 주실 수 있나요??

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