10816번 - 숫자 카드 2
한 40프로까지 진행되다가 시간초과뜨는데 , ,뭘더줄여야할까요 ?
결과값은 잘나와요 !
count가 굉장히 비효율적인 것 같네요.
이분탐색으로 숫자의 위치만 파악하고 그 지점에서 왼쪽 오른쪽으로 일일이 세는 것이 아니라 lower bound, upper bound를 구현하셔야 할 것 같습니다.
정렬하고 해당 카드의 위치를 찾아서 인덱스 반환하는 알고리즘이 비효율적이에요.
최악의 경우 정렬( O(N^2) ), 평균 (O(NlogN) 이고 탐색과정도 효율적으로 보이진 않습니다..
참고로 Counting sort로 해도 자바에서 800ms가 나올정도로 데이터양이 많습니다.
sort메소드보단 counting정렬로 해보시는 것이 어떠실지요.
댓글을 작성하려면 로그인해야 합니다.
tjdals333 3년 전
한 40프로까지 진행되다가 시간초과뜨는데 , ,뭘더줄여야할까요 ?
결과값은 잘나와요 !