mesahwi   5일 전

나름 최적화했다고 생각하는데 시간 초과가 나오네요

제 풀이 방법은  :

방문한 노드를 black에, 방문 중인 노드를 gray에 넣으며 dfs하는 것입니다.

gray에 있는 노드를 다시 방문했을 경우 그 index를 이용해 cycle되는  노드의 수를 계산했습니다.


부탁드립니다ㅜㅜ 도와주세요


atomzeno   5일 전

코드를 안 읽긴 했지만 아마 n2인 거 같네용(모든 정점에서 dfs를 돌리면 안됨...check를 해서 방문한 정점은 다시 방문하지 않게 해야함)

제 생각으로는 

7
3 1 3 7 3 4 6

를 예로 들면

1로 탐색을 했을때, 1-3-3이 cycle이 되니까, 1-X, 3-O로 표시하고

2로 탐색을 했을때, 1은 방문한 적이 있으므로 X

3은 O

4는 4-7-6-4 cycle이므오 4,6,7에 O를 표시

5는 5-3탐색에서 3은 방문한 적이 있으므로 X

이렇게 짜면 O(n)될듯한데....


mesahwi   5일 전

답변 감사합니다ㅎㅎㅎ

그런데 38~45줄의 cycle2()에서 

전에 들린 점들은 제외한다는 걸 구현했는데(정확히는 40줄)

그렇게 하는게 아닌가요?

atomzeno   5일 전

.contains 함수의 시간복잡도가 O(1) 맞죠?

djm03178   5일 전

단순 링크드 리스트이기 때문에 contains는 평균적으로 리스트를 반 돌아야 됩니다. O(N)입니다.

atomzeno   5일 전

.contains 말고 배열 쓰세용...

mesahwi   4일 전

하하 감사합니다

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