twkim8548   1년 전

어느 부분을 수정하면 시간이 좀 줄어들까요..? 

코드는 맞는듯 한데 비효율적으로 짰나 봅니다..

conu   1년 전

파스칼의 삼각형에 대해 알고 계신가요?

BothEarRim   1년 전

시간초과의 원인은 removeFirst()을 너무 많이 호출하기 때문입니다.

배열 앞쪽에 값을 삽입하거나 배열 앞쪽 요소를 삭제하는 연산은 O(N)으로 느린 편에 속하기 때문에 반복해서 여러번 호출하는 것은 좋지 않습니다.

이 문제에서는 크기가 최대 2,000 인 문자열이 2개 주어지므로 N ≤ 4,000 입니다.

25번째 줄 while 문에서 최초 크기 N이 2가 될때까지 총 N-2 번 반복하니까 O(N)이고, 35번째 줄에서 size 만큼 반복하고 있습니다. 이 역시 O(N) 입니다.

따라서 총 O(N2) 번 removeFirst() 를 호출하게 됩니다. removeFirst() 를 한 번 호출할 때 시간 복잡도는 O(N) 이므로 위 코드의 총 시간 복잡도는 O(N2 × N) = O(N3) 입니다.

그래서 시간 초과가 발생합니다.

구현을 바꿔서 removeFirst() 를 쓰지 않고 풀면 통과할 것입니다.

twkim8548   1년 전

감사합니다.. 

removeFirst()를 사용하지 않는 방법을 생각해서 풀어보니 맞았네요 

야매로 푼것 같은데..


시간날때 파스칼의 삼각형 공부해볼 수 있도록 하겠습니다.


두분 모두 감사합니다!

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