2022/03/24) 12. 마구간 정하기(결정알고리즘) [정렬과 그리디, 결정알고리즘]

1. 문제

<마구간 정하기>
: N개의 마구간이 수직선상에 있다. 각 마구간은 x1, x2, x3, ..., xN의 좌표를 가지며, 마구간 간에 좌표가 중복되는 일은 없다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 걸 좋아하지 않는다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 배치하고 싶다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성한다.
가장 가까운 두 말의 최대 거리를 출력하라.

2. 해결 방법

1. 마구간 좌표를 정렬(sort)한다. 그러면 1 2 4 8 9가 된다. 1과 2는 거리가 1이고, 1과 4는 거리가 3이다. 제발 문제를 이상하게 해석하지말자... (4이라는 이름을 가진 마구간, 8이라는 이름을 가진 마구간이라고 생각하고 바로 옆자리네 이러고 앉아있네ㅋㅋㅋ 마구간4와 8은 떨어져 있다.)
2. lt와 rt의 값을 구하여 mid값을 구해야 하는데, 이 lt와 rt를 정하는 기준은 마구간의 최소거리와 최대거리다. 그러므로 lt는 arr[0]이 될 수 없다. 최소거리는 무조건 1이 될 수 밖에 없다.(좌표 겹치지 않는다고 했으니까)
   정리하면 lt는 1로 초기화하고, rt는 arr[length-1](정확하게 따지면 9-1이여야 할 듯. 근데 이분검색할 때 rt값은 크게 영향을 미치지 않는다고 하니 일단 이렇게 패스)
3. solution함수는 count함수에 arr와 mid값을 넘겨서 return된 값에 따라, lt, rt, mid값을 정하는 함수다.(lt와 rt값으로 인해 도출된 mid값이 핵심임! lt와 rt는 mid값을 얻기 위한 거에 불과함)
4. count함수에서는 변수 ep(end point)에 말이 들어간 마구간번호를 넣는다. 그렇게 해서 배열 for문 돌려서 arr[i]-ep >= mid 가 되면 cnt++;를 하고 ep값을 arr[i]값으로 바꿔준다.

3. 정답

        <script>
            function count(stable, dist){ //mid에 따른 마리수가 몇마린지
                let cnt = 1, ep=stable[0];
                for(let i = 1; i < stable.length; i ++){
                    if(stable[i]-ep >= dist){ //조건식생각
                        cnt ++;
                        ep = stable[i];
                    }
                }
               return cnt;
            }
            function solution(c, stable){
                //두 말의 최대거리를 출력하라.
                let answer = 0;
                stable.sort((a,b) => a-b);
                let lt = 1;
                let rt = stable[stable.length-1];
                while(lt <= rt){
                    let mid = parseInt((lt+rt)/2);
                    if(count(stable, mid) >= c){ //부호생각
                        answer = mid;
                        lt = mid+1;
                    }else{
                        rt = mid-1;
                    }
                }
                return answer;
            }
            let arr=[1, 2, 8, 4, 9];
            console.log(solution(3, arr));
        </script>

4. 소감

문제 해석이 안된다. 바본가..?;; 문제 이해를 못해서 1 2 8 4 9 를 sort하지 않고 뭔소린가 하며 보고 있었다. 결과는 정리해서 하는 거였음! 왜 ep를 저걸로 초기화해서 단정시켜버리지?