tn841   2년 전

BFS 위상정렬과 dp배열을 활용해 동적계획법으로 풀었습니다.

질문 게시판에 있는 모든 테스트케이스에 대해 정답이 도출되는 것을 확인하였는데요..

채점 33%에서 시간초과되는 이유를 모르겠습니다.


조언해주시면 정말 감사하겠습니다..!


chogahui05   2년 전

33%에서 시간초과라..

일단 1번째로.. 가비지가 너무 많이 생겨서

gc가 돌기 때문에 생기는 문제 같습니다. 규칙 수가 10만개까지 되다 보니..


TC 수에 따라서는 충분히 가비지가 많이 쌓일 수 있어요. 일단 이 문제가 있고요.

 (arrayLIst에 10만개를 넣으면 실제 메모리 할당 크기는 10만개만큼이 아닙니다. 그보다 더 큽니다)

chogahui05   2년 전

더 결정적인 원인이 있습니다.

 ArrayList의 remove 함수의 시간 복잡도는 O(n)입니다.

그럴 수 밖에 없는게요. ArrayList는 동적 배열입니다.


앞에 '동적'이라는 말만 붙었지 사실상 배열이기 때문에

특정 위치에서 삽입을 하거나 삭제를 하는 경우에, 뒤에 있는 원소들을 앞으로 당기거나, 뒤로 이동시켜야 합니다.


위 코드에서 ArrayList의 최대 크기는 규칙수인 10만입니다.

60번째 줄에서 79번째 줄을 한 블록으로 봤을 때

바깥에 있는 for문은 10만번. 

그리고 안에 있는 remove 함수는 10만번. 이 둘을 곱하면 100억번 나오는군요.


ps.

자잘한 optimize도 필요할 듯 싶군요..

tn841   2년 전

상세한 답변 정말 감사합니다.


ArrayList를 사용한것이 문제가 됐군요..

조언해주신 것들 개선해서 해결해보도록 하겠습니다!!!



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