conu   1년 전

채점 현황을 보면 모든 분들이 C 아니면 C++으로 푸셨던데 그냥 제가 코드를 잘 못 짜서 시간초과가 나는 건지 애초에 파이썬으로는 못 푸는 문제인 건지 궁금합니다

만약 코드를 보여드려야 한다면 보여드릴 수도 있습니다

seawon0808   1년 전

입력 받을 때 sys를 사용해 보시고 pypy로 제출해보시면 될 수도 있습니다.

conu   1년 전

이미 그렇게 했는데도 시간초과가 나네요... 어떤 게 문제인지 모르겠네요

vmffotltka   1년 전

어떻게 접근하셨나요? 코드좀 보여주시겠어요?

conu   1년 전

지식이 별로 없긴한데... 일단 답은 맞게 나옵니다

conu   1년 전

131번째줄은 무시해주세요

vmffotltka   1년 전

자료구조를 deque를 쓰지 마시고 set을 써보시겠어요? deque에서 원소를 찾을 때 최악에 O(n)이 걸리지만 set은 O(1)이 걸립니다. 그게 원인인 것 같습니다.

conu   1년 전

84번째 줄에서 정렬하면 0번 인덱스가 최솟값이니까 정렬한 다음부터 popleft()로 최솟값을 가져왔는데 set으로 해도 그런 게 가능한가요..?

vmffotltka   1년 전

저는 sorted를 사용해서 최소값을 구했습니다. 최소의 소수를 구한 다음 다른 set에도 삭제하는 식으로 했습니다. 문제는 삭제할 때인데, del 연산도 최악의 경우 O(n)입니다.

vmffotltka   1년 전

한 가지 더 힌트를 드리자면, 99~106줄과 121~128줄에서 삭제할 때에 모든 곳을 순회할 필요가 없습니다.

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