kim_victory123   7달 전

이분 탐색으로 풀었습니다.

<질문>

1.그냥 이분 탐색으로 풀면 무조건 시간 초과 나나요?

2.그렇지 않다면 어떤 부분에서 시간 초과가 나나요?


답변 부탁드립니다 ㅠㅠ

luckyandykang   7달 전

같은 값이 많이 중복될 때 시간 초과가 발생합니다.

극단적인 예시로

500000

0 0 0 ... 0 (500000개)

500000

0 0 0 ... 0 (500000개)


위와 같이 입력되면 시간 초과가 발생합니다.

힌트를 드리자면, 위와 같이 같은 값을 모두 탐색하는 대신 배열 A에서 x 이상인 값을 찾는 이분 탐색과 x 초과인 값을 찾는 이분 탐색을 이용하면 문제를 해결할 수 있습니다.

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