시간을 줄일 수 있는 방법을 말씀드릴게요.
1. 28줄
20만이라는 m의 인풋이 들어오면서 계속해서 정렬을 진행중에 있습니다. 정렬을 한 번 하는데 드는 비용은 O(NlogN)이므로 매우 비효율적으로 보입니다.
모든 인풋을 받고나서 정렬을 하면 좋을 것 같아요.
2. DFS탐색 부분
방문 순서를 알아야 하기에 방문처리를 뒤늦게 하신것 같아 보이는데 이는 매우 비효율적입니다.
문제의 예제로 생각해보면 1번 정점에서 => [4,2] 가 들어오고 2번 정점에서 [4,4,3] 이런식으로 중복되는 값들이 계속해서 들어옵니다.
아마 스택보다는 재귀적으로 다시 짜보시는게 좋아보입니다. 해당 노드를 방문 할 때 방문처리를 하시면 효율적으로 짜실 수 있을 겁니다.
3. 10번째 줄
방문처리에 대한 부분입니다.
python에서 list에서 원하는 값을 찾는 in연산에 대한 시간복잡도는 O(N)입니다. 즉, 리스트의 길이만큼 순회를 하여 값을 찾는다는 뜻입니다.
O(1)로 방문을 했는지 안 했는지 처리할 수 있습니다. 한 번 생각해보시면 좋을 것 같아요.
incarceron 1년 전
어제부터 재귀로 해보다가 안돼서
오늘은 스택으로 해봤는데 계속 시간 초과가 나오네요 ㅠ
어떻게 고칠지 감이 오질 않아서 질문에 올립니다.
자그마한 조언이라도 주시면 감사하겠습니다!