23309번 - 철도 공사
연결리스트 탐색 시간복잡도는 O(n) 아닌가요?
해당 문제를 위해 기존에 생성되어있던 역 N개, 고유번호 i를 찾기 위해 공사하는 횟수인 M을 곱하는
O( N * M )이 해당 문제의 시간복잡도인것 같은데 시간초과가 뜨네요...
연결리스트 탐색에서 순차접근외에 다른 탐색방법이 있을까요?
이 문제를 보게되면 각 역들이 연결되어있지만 실제로 필요한 정보는 각 역마다 앞의 역과 이전 역의 고유번호밖에 없습니다.
따라서 각 고유번호마다 앞의 역과 이전역의 고유번호만 저장해주고 쿼리마다 알맞게 조절해주시면 됩니다.
추가로 역의 개수가 N이긴 하지만 여기서는 고유번호를 사용한다는 것을 생각하면
1000000 * 1500000 = 1.5 * 10^12 이므로
각 쿼리마다 O(고유번호 개수)가 아닌 O(1)의 복잡도로 접근하셔야합니다.
감사합니다 덕분에 해결했습니다!
저도 똑같이 시간초과가 뜨는데 어떻게 해결하셨는지 자세히 설명해 주실 수 있나요??
댓글을 작성하려면 로그인해야 합니다.
jeha0714 2년 전
연결리스트 탐색 시간복잡도는 O(n) 아닌가요?
해당 문제를 위해 기존에 생성되어있던 역 N개, 고유번호 i를 찾기 위해 공사하는 횟수인 M을 곱하는
O( N * M )이 해당 문제의 시간복잡도인것 같은데 시간초과가 뜨네요...
연결리스트 탐색에서 순차접근외에 다른 탐색방법이 있을까요?