ufo6475   2년 전

안녕하세요 1342번 문제를 풀다가 의문이 생겨 질문 드립니다.

저는 이 문제를 파이썬 언어를 사용하여 전형적인 백트래킹 형식으로 가능한 모든 경우의 수를 검사하여 결과를 도출해내었습니다. (제출번호 36667316)

하지만 해당 문제에서 abcdefghij 같은 입력이 들어올 시에 시간초과가 나게 되었습니다.

그래서 해당 문제에 대한 검색을 진행 하다 같은 알고리즘을 c++로 작성했을 때 통과되는 모습을 보였습니다.(제출번호 36667263)

제가 작성한 코드에서는 현재 문자열을 check 하는 과정도 더 최적화 되어있는데 시간 초과가 발생합니다.

이렇게 언어에 따라 같은 알고리즘의 문제 정답 여부가 달라지기도 하나요?? 아니면 제 코드 상에 뭔가 다른 시간 초과를 낼만한 요소가 있는 것일까요? 

감사합니다

0000000000   2년 전

파이썬이 원래 극도로 느린 언어입니다.

ufo6475   2년 전

그렇다면 해당 문제는 파이썬으로 백트래킹만을 써서는 풀수 없는 문제인가요?

wizardrabbit   2년 전

안녕하세요?

preview

질문을 보고 해당 문제를 제가 직접 파이썬으로 풀어서 제출해 보았습니다. PyPy3, Python 3 모두 통과했습니다.

다만 실행 시간 차이를 보면 아시겠지만, Python 3의 경우 본 문제의 제한시간인 8초(2 * 3 + 2)인 것을 생각하면 매우 간당간당하게 통과했음을 알 수 있습니다. 즉 이 코드를 다시 제출하거나, 알맞은 알고리즘을 써도 조금만 비효율적인 코드였다면 통과하지 못 했을 수도 있다는 것입니다.

Python 3은 대부분의 경우 PyPy3보다 더 느리게 동작하므로 본 문제처럼 실행 시간이 길 수 있는 문제에서는 PyPy3으로 제출하는 것이 좋습니다.

질문자님의 코드 역시 PyPy3으로 제출한 결과 1000ms 내외로 통과했습니다. 그러니 Python 3보다는 PyPy3을 사용해서 작성하신 코드를 다시 제출해 보세요.

ufo6475   2년 전

그런 것이었군요. 다음부터는 pypy를 쓰도록 하겠습니다. 감사합니다.

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