파이썬 시간 초과 관련 질문드립니다

1. 시간복잡도는 찾고자 하는 숫자 기준으로 mlog(n)이 발생하는 것 같습니다. 

2. 최악의 경우를 가정(m=500k, n=500k로 지정할 경우, 660만정도의 값이 나오는 것 같습니다)

3. 아래와 같이 코드를 짯는데, 코드의 내용은 다음과 같습니다. 

 a) 이진탐색으로 접근해서

 b) 만약 찾고자 하는 값이 mid 값에 오면

 c) 현재의 left 좌표와 last 좌표의 범위 내에서 찾고자 하는 값이 몇개 있는지 세어줍니다.     

    left 좌표부터 올라오다가 가장 먼저 만나는 값이 찾고자 하는 중복수열 (예를 들면, 1 1 1 1 1 1 1 의 가장 왼쪽 1) 가장 왼쪽값. 그리고 break

   last 좌표부터 내려오다가 가장 먼저 만나는 값이 찾고자 하는 중복수열의 가장 오른쪽값. 그리고 break

  d) last 좌표 - left 좌표 + 1이 찾고자 하는 문자값이 몇개 있는지 나타냄


1-2-3을 계속 반복하는 식으로 진행했습니다.

계속 시간 초과가 발생하는데... 혹시... 어떤 부분을 좀 더 신경써보면 괜찮을까요...? 

nahwasa   1년 전

c번로직이 생각보다 더 걸리실꺼에요!

500000
1 2 3 4 ... 500000
500000
250000 250000 250000 250000.... 250000

이런식의 테스트케이스라면 얼마나 걸릴지 감이 오시겠죠?!

c번 로직도 이분탐색으로 찾으실 수 있어요. c++에서는 라이브러리로 제공해줘서 흔히들 쓰는 lower_bound, upper_bound가 이분탐색을 좀 변경해서 찾아내는겁니다.

위 lower_bound, upper_bound를 키워드로 검색해서 구현해보시는걸 추천드립니다.

혹은 아예  로직을 다르게 생각해보시는것도 추천드립니다.

갯수를 미리 세어두신다거나! 그럼 c로직은 필요없어지구요.

아니면 아예 이분탐색을 쓰지 않는 방식중에서는 메모리는 좀더 쓰지만 O(N + M)으로 가능한 녀석도 있습니다!

nahwasa님 감사합니다. 우선은 카운팅 함수로 풀었습니다.

말씀해주신 로직은 더 찾아서 공부해보겠습니다. 

nahwasa   1년 전

위에서 말한 이분탐색을 쓰지 않고 하는 방식은

해쉬맵 자료구조를 사용해 진행하시면 됩니다. (파이썬으로 뭔진 잘 모르겠어요. 아마 Dictionary ?)

아직 코린이라 그쪽까진 보지 못했는데, 고거 한번 더 공부하고 다시 한번 또 풀어보겠습니다 ㅎㅎ 답변 고맙습니다~! 

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