입력 받을 때 sys를 사용해 보시고 pypy로 제출해보시면 될 수도 있습니다.
4703번 - 그림의 추측
입력 받을 때 sys를 사용해 보시고 pypy로 제출해보시면 될 수도 있습니다.
어떻게 접근하셨나요? 코드좀 보여주시겠어요?
자료구조를 deque를 쓰지 마시고 set을 써보시겠어요? deque에서 원소를 찾을 때 최악에 O(n)이 걸리지만 set은 O(1)이 걸립니다. 그게 원인인 것 같습니다.
저는 sorted를 사용해서 최소값을 구했습니다. 최소의 소수를 구한 다음 다른 set에도 삭제하는 식으로 했습니다. 문제는 삭제할 때인데, del 연산도 최악의 경우 O(n)입니다.
한 가지 더 힌트를 드리자면, 99~106줄과 121~128줄에서 삭제할 때에 모든 곳을 순회할 필요가 없습니다.
댓글을 작성하려면 로그인해야 합니다.
conu 1년 전
채점 현황을 보면 모든 분들이 C 아니면 C++으로 푸셨던데 그냥 제가 코드를 잘 못 짜서 시간초과가 나는 건지 애초에 파이썬으로는 못 푸는 문제인 건지 궁금합니다
만약 코드를 보여드려야 한다면 보여드릴 수도 있습니다