mo0nlight0   4년 전

안녕하세요. 배열로 구현할 생각도 안 해보고 연결 리스트로 구현하는 것에 먼저 손을 대버리는 바람에 2일째 고생을 하고 있는 컴린이입니다.

드디어 예제를 출력하면 나오긴 하고, 여러가지 제가 생각한 테스트 케이스들을 넣어보았을 때 잘 굴러가기에 제출을 해보았습니다.

그런데 무려 시간초과가 났습니다.

제 짧은 지식으로는 이유를 알아낼 수 없어 질문 드립니다. 어떤 점에서 문제가 있어 시간초과를 맞았는지 문의드립니다.

djm03178   4년 전

큐의 head만 기억하고 tail을 기억하지 않으면 효율적인 큐를 만들 수 없습니다. 22, 59번째 줄처럼 마지막을 찾아 끝까지 들어가야 하기 때문에 N개의 원소를 삽입하는 것이 O(N^2) 시간이 걸리기 때문입니다.

또한 size 역시 끝까지 찾아들어가면서 셀 필요가 없습니다. push할 때마다 카운트를 늘리고, pop할 때마다 카운트를 감소시키기만 하면 됩니다.

mo0nlight0   4년 전

덕분에 해결했습니다 감사합니다!

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