반례: 2147483647 198726497 100987253

정답: 67561299

출력: 시간초과

lst에 담기는 수가 n^1, n^2, n^3, ...를 d로 나눈 나머지가 맞죠?

최대 숫자로 해도 금방 나오는 이유는 그게 가장 오래 걸리는 경우가 아니기 때문입니다. 가장 오래 걸리는 경우는, 루프를 돌릴 때 x가 매우 긴 사이클을 이뤄서 lst가 밑도 끝도 없이 길어지는 경우입니다. 이런 일이 발생했을 때 9행에서 lst의 원소를 일일이 하나씩 보면서 x가 있는지 확인하기 때문에, lst의 길이가 x까지 길어진다면 위 코드의 시간복잡도는 O(x^2)이 됩니다.

또다른 문제도 있는데요, 위 문제는 집합 자료형을 사용하면 in 연산이 O(1) 안에 이뤄지므로 lst의 길이 x에 대해 O(x) 안에 코드가 종료되기는 합니다. 하지만 O(x)인 코드라고 하더라도 시간 내에 코드가 종료될 수 없습니다. 입력 "2147483647 2147483647 2000000009"에 대해 lst의 길이는 142,857,143개까지 늘어나며, 실제로 이 입력을 넣어보시면 코드가 절대 종료되지 않는 걸 확인하실 수 있습니다. 메모리 제한 문제도 있어서, 1억 개가 넘는 수를 전부 리스트에 저장할 수도 없습니다.

발상은 좋았는데, 아쉽네요. 분할정복을 통한 거듭제곱, 또는 이진법을 활용한 거듭제곱에 대해 공부해보시고 푸는 걸 추천드립니다.

추가로, 오답을 출력하기도 합니다. 아래 입력을 넣어보세요.

다들 답변 감사합니다 ..!

저는 무조건 반복이 일어나서 금방 끝날 줄알았는데 아니었네요