프로그래머스 - 징검다리 (JAVA)

문제 링크

 

 

문제 풀이 과정

이 문제를 처음 접했을 때 어떤 접근 방식을 이용하여 풀어야할지 고민을 많이 했다.

결국은 이 문제의 답은 이진 탐색을 이용하는 것이다.

 

이진 탐색으로 바위 간격의 최소값을 mid 값으로 정해두고 해결하면된다.

 

바위의 간격은 항상 정렬 되어 있지 않으므로 정렬 한 뒤에 시작한다.

정렬하고 나면 바위의 간격은 {2, 9, 3, 3, 4, 4} 가 된다.

 

 

여기서 중간 값은 14가 된다.

 

첫번째 바위와 의 거리가 2이고, mid 값보다 작으므로 바위를 한개를 제거해준다.

그러면 바위의 간격이 11이 된다. 

 

11은 mid 보다 작으므로 다음 바위도 제거해준다.

 

첫 바위와의 거리가 14가 되고, mid 보다 같으므로 다음 바위를 검사한다.

 

다음 바위와의 거리가 3이고, 더이상 제거할 바위도 없다. 14가 최소가 될 수 없으므로 mid 값을 줄여준다.

 

0 ~ 14 사이의 mid 값은 7이므로 mid 값을 7로 바꿔 준다.

첫번째 바위와의 거리가 2이고 7보다 작으므로 첫번째 바위를 제거해준다.

 

첫번째 바위를 제거하면 시작 지점에서 두번째 바위까지의 거리가 11이 되고 mid 값보다 크므로 두번째 바위 이후의 바위들의 거리를 검토한다.

 

두번째 바위와 세번째 바위의 거리가 3이므로 mid 보다 작고 추가로 바위를 제거 할 수 있으므로 3번째 바위를 추가로 제거한다.

 

2번째 와 4번째 바위의 거리가 6이 된다.  이 값은 mid 값보다 작으므로 mid 가 최소 거리가 되지 않는다.

다시 mid 값을 줄여준다.

 

다음 mid 값은 0 ~ 7 의 중간 값인 3이 된다.

 

시작과 첫번째 바위의 거리가 2이고 이 값은 mid 값보다 작으므로 첫번째 바위를 제거한다.

그러면 거리가 11이 되고 이 값은 mid 값 보다 크므로 넘어간다.

그 이후의 바위의 거리들을 검사하면 mid 값보다 같거나 크므로 이 값은 바위들의 최소 값이 된다.

 

이 문제는 바위들의 최솟값들 중에서 가장 큰 값을 구하는 문제이므로 구한 최솟값에 + 1 한 상태에서 한번더 검사한다.

 

그다음 mid 값은 4이고

시작과 첫번째 바위의 거리가 2이고 mid 값보다 작으므로 첫번째 바위를 제거한다.

 

 

첫번째 바위를 제거한 뒤 시작과 두번째 바위의 거리는 11이 되고, 이 값은 mid 값보다 크므로 다음 바위를 검사한다.

두번째 바위와 세번째 바위의 거리가 mid 값보다 작으므로 바위를 하나 제거한다.

 

제거한 뒤의 거리는 6이고 이 값은 mid 값보다 크며, 그 이후의 값을 검사했을때 mid 값보다 큰 값이 없으므로 mid 값을 사용 할 수 있다.

 

여기서 구한 mid 값은 3, 4이며 이 중 큰 값은 4이므로 4가 출력 된다.

 

else {
    left = mid + 1;

    if (cnt == n) {
        result = Math.max(result, mid);
    }
}

 

 

구한 mid 값들 중에서 큰 값을 구하기 위해서 Math.max 를 이용했는데 이렇게 구하면 일부 케이스에서 통과가 안된다.

이 코드를 지우고 여기서 result = mid 를 하면 케이스가 통과된다.

 

코드의 의미는 같은 것 같은데 왜 통과가 안되는지 모르겠다.

 

전체코드