algospot   10달 전

제가 작성한 코드는 아래와 같습니다.

그런데, 짜면서도 계속 최악의 경우만을 생각하는 버릇때문에,,

M이 50만이고, 만약 N도 50만에

그러면 50만*50만의 복잡도가 나오는데 (이분검색은 뭐 있으나마나의 상황)

이런경우가 입력이 안들어와서 통과한거같은데,

메모리를 소모해가면서 index 카운팅하는 방법밖엔 없는가요?

아니면 보통 이런류의 최악의문제도 정해풀이법이 그냥 제가 작성한것과 같은가요..?

lsc4719   10달 전

코드의 알고리즘을 조금 설명해 주실 수 있나요?

algospot   9달 전

네~

1)오름차순 정렬

2)목표물 이진탐색으로 검색

3)정렬되었기 때문에 목표물을 중심으로 좌우에 같은게 존재할 수 있으니, 다른게 나올때까지 좌우 cnt++하면서 확장

끝.

..그러니 다시 말해, 자료가 모드 같고 그 자료갯수가 50만개라면,

이진탐색도 한번만 실행되니 있으나마나가 되고,

자료를 찾고 좌우 확장도 50만번 검색이 일어나니

50만*50만이 되면 시간뻑

을 질문한거에요 ㅎㅎ

lsc4719   9달 전

아 그러면 abbbbbbc에서 b의 가장 오른쪽 원소도 binary search로 찾으면 O(mlogn)이니까 해결될 것 같아요.

algospot   9달 전

아 물론, break도 추가해야겠네요

lsc4719   9달 전

M개의 쿼리마다 binary search O(lgN)을 사용하니까  O(M*lgN)이 되겠죠?ㅐ

lsc4719   9달 전

아 빼먹은게 있었네요. N개의 정수를 정렬하는데 O(NlgN)이니까, 결국 O(max(MlgN, NlgN))이 되겠네요ㅑ8

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