[Programmers - 이분검색] 예산

프로그래머스(Programmers) 예산 - 문제보기

Level3임을 감안하면 쉬운 문제였지만 몇 가지 생각할 점이 있었다.
풀이를 시작하며 low값을 가장 적은 요청금액으로, high값을 가장 높은 요청금액으로 잡고 이분탐색을 실행하였다. 이때, 아래의 1, 2번이 문제가 되었다.

1. 각 지방에서 요청한 예산의 총 합이 정부예산보다 적을 경우

   이런 경우 모든 지방이 요청한 만큼 예산을 받을 수 있다. 따라서 예산 상한선은 가장 많은 금액을 요청한 지방의 금액이 된다.

2. 정부예산이 가장 적은 요청금액보다도 적을 경우

   처음에 low값을 가장 적은 요청금액으로 잡았기 때문에 위의 경우는 탐색범위에서 벗어난다. low를 1로 변경할까 하였지만 위의 경우를 미리 체크해주고 low값은 그대로 가져가기로 하였다.

3. 각 지방에서 요청한 금액의 합이 int 범위를 넘어서는 경우

   알고리즘 문제의 단골 오류 범인인 자료형 범위초과... 분명 처음 문제를 읽으며 습관적으로 int범위를 확인하였다. 하지만 정부 예산이 최대 1,000,000,000이여서 각 지방 요청금액의 합이 이 두배(int범위 -2,147,483,648 ~ 2,147,438,647)를 뛰어넘을 경우를 생각하지 못했다. 총 합을 저장하는 변수를 long타입으로 변경하였다.

답안 코드