listdata.count는 listdata의 원소를 쭉 둘러보는 데다가 안에 중복된 원소도 많이 들어가 있어서 매우 비효율적입니다. listdata와 result 대신 N이 10^6 이하이므로 크기 N+1짜리 배열 A를 만들어서 x가 등장한 적 있으면 A[x]=1, 아니면 A[x]=0이도록 하는 방법이 있습니다.

count쪽은 말씀해주신 방법으로 개선하면 확실히 좋을 것 같네요 감사합니다!

그나저나 19~21행을 실행시키기 전에 recursion depth 오버플로우가 생깁니다ㅠㅠ

근데 func([17]) 같이 입력해보면 제대로 돌아갑니다. 의도한 방식대로 작동하는걸 확인했는데

왜 선언하는 과정에서 오버플로우가 생기는걸까요??

질문 자체랑 상관없는데 값 비교에 is 쓰면 예상치 못한 결과가 일어날 수 있어요. is 는 두 값이 진짜 같은 object를 가리키는지 확인하거든요. 아마 is 대신 == 을, is not 대신 != 을 쓰셔야 할 거예요.

list에 1이 들어있나를 확인하는 거니까 `1 in listdata`같은 방법을 쓸 수 있어요. 이렇게 하면 첫번째로 1을 확인했을 때 바로 True를 반환해서 더 효율적이예요.

그런데 저같으면 listdata를 list 대신 set으로 할 것 같네요. set을 쓰면 hash를 써서 `1 in listdata`을 확인할 때 걸리는 시간이 더 짧아요.

지금 그리고 이 함수를 재귀호출 없이 구현할 수 있거든요. while 문 써서요. return func(new, counter)의 new랑 counter를 그대로 listdata랑 counter에 대입하고 위로 올라간다는 느낌으로 생각하면 이해하기 쉬우려나요.

일단은 수정한 코드를 붙여놨어요.

그나저나 19~21행을 실행시키기 전에 recursion depth 오버플로우가 생긴다고 하셨는데, 에러 메세지 볼 수 있을까요?

recursion error는 갑자기 사라졌네요;;

답변 감사합니다!