카카오 2019 인턴 - 징검다리 건너기

phoenixKim·2021년 10월 8일
0

카카오 기출문제

목록 보기
22/24

참고 사이트

https://eunchanee.tistory.com/94

풀이전략

-> 제한 사항에서 stone의 값이 최대 20억이다.
logN으로 나타낼수 있는 방법을 고찰하면 우선순위 큐나 unordered종류, 이분 탐색인데


-> 그림 과정을 통해서 순차를 조작하면 안되는 것을 파악할수 있으므로
반드시 이분 탐색을 이용해야 한다.

=> 그런데!! 이분탐색 타겟팅을 어디에 적용할지를 파악하지 못했다.

쉽게 생각해보면 징검다리의 카운트 수를 이용해 진행하면 된다.
현재 2,4,5,3,2,1,4,2,5,1 이 존재하는데
min : 1 / max : 5 라고 하고 진행하면 mid : 3 이다.
value - mid < 0으로 진행하는 방식으로
연속된 카운트값이 k일 경우 확인하는 방식으로 접근하면 쉽게 테스트 케이스가 가능하다!

profile
🔥🔥🔥

0개의 댓글

관련 채용 정보