원래 이런 종류의 문제를 잘 올리는 편은 아니지만 오늘만큼은 좀 더 올리고싶었다. 이 문제는 자칫 하면은 어떤 유형일지 모를수도 있는 타입인데 잘 읽어보면은 binary search 의 특성이 많이 보이는 질문이다. 먼저, m이라는 공의 개수가 주어지고 position이라는 벡터가 있을때 공을 배치할수있는 가장 큰 간격을 구하는 문제이다.
이문제를 자세히 살펴보면은, 프로그래머스 레벨3의 징검다리 건너기가 떠오르기도 하고 혹은 KoKo eating Banana가 떠오르기도 한다. 여기서 중요한거는 우리는 가장 큰 간격을 모르기 때문에 포지션의 최대값, 그리고 1과의 간격중 중간 값을 구한다음에 "이 간격으로 공을 배치할 경우 m만큼의 숫자가 나오는가?" 에 대한 답을 찾으면 됐었다.
꽤 많은 부분이 예전에 풀었던 binary search 유형을 따라갔다. 가장 먼저 중간값을 구한다음에 공을 배치하는 함수를 작성한다음에 공에 개수가 m 과 같다면 계속해서 최대값을 구할때까지 left 를 mid+1 로 진행해주었다.
배운점:
1. Binary Search 의 비슷한 유형
2. 문제 잘 읽기
성장하는 사람