문제

링크텍스트

풀이

이 문제가 왜 이분탐색으로 풀어야 하는지 딱 알수가 없었다 그냥 브루트포스로 푸려고 했는데 복잡도가 터무니 없음. 최대 20만개의 배열이 2억의 값을 가질 수 있기 때문에 단순 비교해서 풀경우 간단한 테케는 되지만 효율성이 전부 나락갔을 것 같다

한개의 징검다리가 k값을 가지면 k명 초과로는 건너갈 수 가 없는 것을 가지고 mid값을 조정하면서 해당 mid값이 건너갈 수 있는 사람들을 조정할 수 있게된다.

1. 한번에 건너뛸수 있는 개수가 k개 이상이 되면 반환

			for (int stone: stones) {
                if (stone - mid <= 0) {
                    cnt += 1;
                } else {
                    cnt = 0;
                }
                if (cnt >= k) {
                    break;
                }
            }

연속해서 건너지 못하는 개수(한번에 건너 뛰어야 하는 개수)가 늘어나면 다음 사람이 건너지 못하기 때문에 바로 반환된다

2. 건너 가는 사람의 범위를 재 정의 해준다

			if (cnt >= k) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }

건너가는 사람이 k보다 크다는 것은 현재의 값이 너무 크기 때문에 max값을 좁혀 주어야 한다.

이분 탐색 문제야 말로 이문제가 어떻게 이분탐색으로 접근 할 수 있는지에 대한 전략을 가지고 풀어야 효율성에서도 더 좋은 코드가 나오는 것 같다

전체 코드

전체 코드