다소 조심스러운 요청입니다만, 문제의 제한이 O(N^2)이나 O(N^2 * (길이))등의 풀이의 통과 여부에 애매한 스탠스인 것 같아서 글을 올립니다.
먼저, C++로 다음과 같은 O(N^2)의 코드가 통과됩니다. https://www.acmicpc.net/source... merge 과정에서 크기 20001(=N)의 string 배열을 매번 선언하고 있기에 N^2의 시간이 걸리는 코드이지만 정확히 1초 정도가 소요됩니다.
이 코드들이 통과되는 것은 내장 비교 함수들이 매우 빠른 연산들을 사용하기 때문이므로 직접 모든 로직을 구현한 제곱 풀이는 통과되기 어렵습니다. 지금의 2초 시간 제한은 이러한 점에서 애매하다고 생각합니다. 매우 오래된 문제라 제한이 느슨한 것이라고 생각되는데, 평범하게 O(N*log(N)*(길이))에 동작하는 코드는 C++ 기준으로 0.1초를 넘지 않습니다. 0.3초나 그에 근접한 시간 제한으로 줄이고, Python 등도 시간 제한이 1초가 넘지 않도록 조정을 했으면 합니다. (개인적으로는 기본 보너스의 +2초 부분이 너무 커서 이런 케이스에서 자주 문제를 일으킨다고 생각합니다.)
djm03178 2년 전 2
다소 조심스러운 요청입니다만, 문제의 제한이 O(N^2)이나 O(N^2 * (길이))등의 풀이의 통과 여부에 애매한 스탠스인 것 같아서 글을 올립니다.
먼저, C++로 다음과 같은 O(N^2)의 코드가 통과됩니다. https://www.acmicpc.net/source... merge 과정에서 크기 20001(=N)의 string 배열을 매번 선언하고 있기에 N^2의 시간이 걸리는 코드이지만 정확히 1초 정도가 소요됩니다.
Python으로는 https://www.acmicpc.net/board/... 에 있는 무려 O(N^2 * (길이))가 통과됩니다. (길이) 부분이 내장 함수이기 때문에 보너스 시간이 무의미하게 매우 빠릅니다. https://www.acmicpc.net/source... 비교가 최대한 오래 걸리도록 하는 데이터도 만들어봤지만 3.8초 정도밖에 걸리지 않았습니다. PyPy로는 더 빠르지만, 비교 로직이 느린지 이 데이터에서는 7.8초로 크게 시간이 늘어납니다. https://www.acmicpc.net/source...
이 데이터를 우선 추가 부탁드립니다. data.zip
이 코드들이 통과되는 것은 내장 비교 함수들이 매우 빠른 연산들을 사용하기 때문이므로 직접 모든 로직을 구현한 제곱 풀이는 통과되기 어렵습니다. 지금의 2초 시간 제한은 이러한 점에서 애매하다고 생각합니다. 매우 오래된 문제라 제한이 느슨한 것이라고 생각되는데, 평범하게 O(N*log(N)*(길이))에 동작하는 코드는 C++ 기준으로 0.1초를 넘지 않습니다. 0.3초나 그에 근접한 시간 제한으로 줄이고, Python 등도 시간 제한이 1초가 넘지 않도록 조정을 했으면 합니다. (개인적으로는 기본 보너스의 +2초 부분이 너무 커서 이런 케이스에서 자주 문제를 일으킨다고 생각합니다.)