kengh2472   9달 전

2458번 키순서 문제에서 원하는 풀이 방향은 플로이드 워셜인 것 같지만 혹시나 하는 마음에 정방향 역방향 그래프를 2개만들어 bfs로 점을 찾아 더한값이 N-1과 같다면 정답값을 +1 하는 방식으로 풀었습니다. 시간초과를 기대한것과 달리 통과를 하였는데 시간복잡도를 계산해보았습니다.

76번째 줄 func(1) + func(2)에서 O(2M) N만큼 돌리니 O(2MN)

2MN == N^3 == 125,000,000 이라서 시간1초 언저리라 가능.

이렇게 시간복잡도를 계산해도 될까요?

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