1766번 - 문제집
방향 그래프라고 두고 풀었습니다.
전부 출력할 때까지 while문을 돌리고, 그 안에서 1부터 n까지 반복문을 돌리는데"출력한 적 없는 진입 차수가 0인 노드"를 발견하면 그 수를 출력하고 노드/간선 제거를 하는 것을 반복했습니다.
저는 1억 번의 연산을 약 1초로 계산하는데 이 코드로는 2초가 넘을 것이라는 예상과 달랐습니다.
입력으로
32000 31999
31999 31998
...
2 1
이 주어졌다고 하면, 1부터 n까지 O(n)으로 탐색하는 제 코드로는
32,000 * 31,999 / 2 = 약 512,000,000 번의 연산을 하는 것 같은데, 맞나요?
인접리스트를 쓸 때 위상정렬의 시간복잡도를 다시 계산해보시면 좋을 거 같습니다.
제출하신 풀이는 실행에 5364ms가 걸렸으나, 언어에 따른 시간 제한 보너스 덕분에 통과된 것입니다. 언어 정보 도움말을 참고하세요.
댓글을 작성하려면 로그인해야 합니다.
choisk0531 11달 전
방향 그래프라고 두고 풀었습니다.
전부 출력할 때까지 while문을 돌리고, 그 안에서 1부터 n까지 반복문을 돌리는데
"출력한 적 없는 진입 차수가 0인 노드"를 발견하면 그 수를 출력하고 노드/간선 제거를 하는 것을 반복했습니다.
저는 1억 번의 연산을 약 1초로 계산하는데 이 코드로는 2초가 넘을 것이라는 예상과 달랐습니다.
입력으로
32000 31999
32000 31999
31999 31998
...
2 1
이 주어졌다고 하면, 1부터 n까지 O(n)으로 탐색하는 제 코드로는
32,000 * 31,999 / 2 = 약 512,000,000 번의 연산을 하는 것 같은데, 맞나요?