1. 가장 시간에 심각하게 영향을 주는 부분은 A를 고르는 부분입니다. 

A에서 1, 2를 제거했을 때와 2, 1을 제거했을 때를 구별하지 못하기 때문에 실제 필요한 횟수의 (N//2)!배만큼 많은 계산을 하고 있습니다.

29~31번째 줄에서 A[i]를 골랐으면 그 이후 호출되는 더 깊은 judge 함수에서는 0~i 를 고르지 않는 방식으로 다시 구현해 보세요. 

필요하다면 함수입력에 변수를 더 추가할 수도 있습니다.

2.  redundant한 계산이 너무 많습니다.

20번 줄에서 A를 통해 B를 계산할 때 set(start)를 사용하는데, 이 과정에서 list를 set으로 변환하는 과정을 매번 합니다.

13번 줄의 경우에도 d와 int(N/2)를 비교하는데 이 int(N/2)는 매번 계산하게 됩니다. 

저렇게 자주 사용하는 값들은 함수 정의 이전에 한 번 저 값들을 계산해 두고 그걸 불러오는 쪽이 좋습니다.

3. start, A, B의 인덱스에 왜 1~n을 사용하신 이유는 단순히 0부터 시작하는 번호가 익숙치 않으셔서인가요?

현재 그 값이 사용된 곳은 18번 줄과 25번 줄 뿐입니다. 다시 1을 뺄 거라면 0~n-1이 자연스럽습니다.

빠른 답변 정말 감사드립니다.

원래 제가 A와 B를 구할 때 리스트로 append를 각각 써서 구했는데, B는 결국 A의 차집합이 될거여서 차집합을 사용하기 위해 set을 사용해 보았습니다. 현재는 append가 시간이 많이 걸리나 싶어서 슬라이싱 형식으로 바꾼 것인데, B를 구할 때 set을 쓸 때보다 슬라이싱 처리가 더 빠를까요?

답변 달아주신 중복제거는 다시 한번 생각해 보면서 구현해 보겠습니다. 감사합니다

다시 해보았습니다.. pypy에서는 1800ms로 되는데 파이썬에서는 아직 안되네요..

전체적으로 수정을 해서 반복은 잡은 것 같습니다만, 아마 B를 결정하는 과정에서 순회가 시간을 잡아먹는 것 같기도 하고, check를 원상태로 돌리기 위한 copy가 오래걸리나 싶기도 한데 이 두 부분을 어떻게 개선해야 될지 모르겠습니다.. 한 번 더 도움 주시면 감사하겠습니다

카피를 하는 것이 오래 걸리는 것이 맞습니다.

check는 전역변수로 놔두고 다음과 같이 할 수 있습니다. 핵심 코드만 아래에 적어 두었는데 참고하셔도 좋고 스스로 생각해 보셔도 좋습니다.

원소를 매번 A[a1], A[a2]로 사용하는 것도 은근히 시간을 많이 잡아먹습니다. 코드가 

for i, a1 in enumerate(A):

    for a2 in A[i+1:]:

등으로 고치는 것만으로도 제 로컬에서 실행시간이 3.7 -> 2.5로 줄었는데 무시하기는 어려운 차이입니다.

first의 첫 원소를 True로 둔 것을 보아 벌써 생각하셨겠지만 사실 이 문제는 실행시간을 뭉텅이로 줄일 깨알같은 요소가 산재해 있습니다.

가령 S를 받은 뒤 S[a][b]+S[b][a]를 다시 S'[a][b]에 저장해 두면 어떨까요? sumA, sumB를 계산하는 시간이 반으로 줄어듭니다.

아마 이 중에 몇 가지만 적용해도 통과가 가능할 것입니다.

@wider93

정말 감사합니다

공부하는 마음으로 세가지 모두 이해하고 적용해보았더니 파이썬으로도 1312ms가 나오네요;;

A[a1]으로 받는 것도 좀 더 깔끔하게 처리할 방법이 없을까 했는데 되게 깔끔한 방법이 있어서 도움이 많이 된 것 같습니다. 이것도 시간을 많이 줄여주더군요.. 다른 두가지 예시도 코드 활용에 도움이 많이 되었고, 시간도 많이 줄여 주었습니다

답변자님이 주신 답변으로 정말 여러가지를 배운 것 같습니다.. 감사합니다