10816번 - 숫자 카드 2
이 문제로 이진탐색이라는 존재를 처음 구글링으로 배우게 되고
리스트에서 이진탐색을 써서 데이터가 있는 위치를 빠르게 알아내는건 좋은데...
그 뒤 그 데이터가 몇개가 있는지 갯수를 세는 로직이 안떠오르네요
찾은 데이터의 위치가 동일한 데이터들의 중앙위치라는 보장도 없을테고...
만일 운좋게 찾자는 데이터들의 중앙이여도
나온 위치로 양옆으로 타겟 데이터랑 같은 데이터인지 비교할려고 한칸씩늘려가자니 수십만개의 데이터가 다 똑같으면
시간이 정말 늘어질것같고
진짜 어떻게 로직을 접근해야할까요?
이진 탐색으로 target이 처음 등장하는 위치와 target를 초과하는 값이 처음 등장하는 위치를 구해보면 좋을 것 같습니다.
https://www.acmicpc.net/blog/v...
위 글에서 질문하신 모든 내용의 답을 찾을 수 있을 겁니다.
온갖 구글링과 Ai의 질답으로 이진탐색의
lowerb bound, upper bound를 알고
최대한 로직을 이해할려고 애쓰고
부등호 몇번 바꿔써보고 종이, 펜으로 시뮬레이션도 돌려보고 할수있는걸 최대한 해보니까
결국 3일만에 풀리긴 하는군요...
비록 시간이 3500대가 찍히긴 했지만 그 시간최적화는
Ai로 구경정도만 할렵니다...
힌트주신 분들 정말 감사드립니다
댓글을 작성하려면 로그인해야 합니다.
qusworud 7달 전
이 문제로 이진탐색이라는 존재를 처음 구글링으로 배우게 되고
리스트에서 이진탐색을 써서 데이터가 있는 위치를 빠르게 알아내는건 좋은데...
그 뒤 그 데이터가 몇개가 있는지 갯수를 세는 로직이 안떠오르네요
찾은 데이터의 위치가 동일한 데이터들의 중앙위치라는 보장도 없을테고...
만일 운좋게 찾자는 데이터들의 중앙이여도
나온 위치로 양옆으로 타겟 데이터랑 같은 데이터인지 비교할려고 한칸씩늘려가자니 수십만개의 데이터가 다 똑같으면
시간이 정말 늘어질것같고
진짜 어떻게 로직을 접근해야할까요?