cardbt   4년 전

안녕하세요.


음.. 질문 검색을 해보니, input값을 배열의 인덱스로 처리해서 문제를 해결 하는 방법도 있더군요. 허나 문제의 카테고리가 이분 탐색에 있었기에 이분 탐색으로 처리하려고 아래 소스와 같이 로직을 작성했습니다.


큰 줄기로 설명을 드리면, 우선 입력을 받고 이걸 퀵정렬로 정렬을 합니다.

그 다음에 찾아야할 숫자의 첫번째 위치와 마지막 위치를 두번의 이분 탐색을 이용해서 구하는 방식으로 처리했습니다.


처음에는 아무 위치나 원하는 숫자의 위치를 구한다믄 작은 수 방향, 큰 수방향으로 카운팅을 할까 했는데, N 50만개가 전부 1이고, 탐색하려는 숫자 M 50만개가 전부 1이라는 최악의 경우에는 죽도밥도 안되겠다 싶어서 이분 탐색 두번으로 처리하게 했습니다.


근데... 그래도 시간 초과네요 ㅠㅠ

뭔가 더 좋은 방법이 있을까요?

doju   4년 전

제시하신 "N 50만개가 전부 1이고, 탐색하려는 숫자 M 50만개가 전부 1이라는 최악의 경우"에서 quicksort가 아주 비효율적으로 동작합니다.

cardbt   4년 전

아.. 그렇군요. O(n^2)가 되겠군요.

망했네요. 퀵정렬로 하면 안되겠군요.

cardbt   4년 전

병합 정렬로 변경해서 해결했습니다.

감사합니다.

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