rhdtka21   4년 전

반례도 넣어봤고, 다른 질문들 글 보니까 저처럼 sorting해서 O(N)번 탐색하는걸로 푸는게 맞는거 같은데

시간 초과가 계속 뜨네요...


고수분들 조언 부탁드립니다 ㅠ

meringueee   4년 전

arr.count(arr[idx]) 이 구문 시간복잡도가 어떻게 되나요? 제생각엔 이부분이 O(N)일것같은데 그러면 최대 O(N^2) 시간복잡도가 됩니다.

기본 기능이라면 sort 여부를 고려하지 않았을 테니까요.

sort하신 후에 binary search로 값이 바뀌는 부분을 찾으시는 게 좋을 듯 합니다.

rhdtka21   4년 전

아 그냥 하나씩 탐색하면서 인접 배열끼리 비교하는걸로 하면 되는걸 굳이 count를 써서 시간복잡도를 늘린거였네요 감사합니다 해결했습니다.

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