[JS] 지형편집

이분탐색을 응용한 방식으로 해결하였다!

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/12984

프로그래머스

 

 

 

제한사항을 처음 읽고 든 생각은 이분탐색이었다. 모든 층을 검사하는건 10억이라는 수치상 말이 안되었기 때문이다.

 

이분탐색을 사용하려면 정렬된 데이터가 필요했다. 층수 자체는 정렬된 데이터긴 하지만 우리가 원하는 건 최소 비용이다. 이는 정렬되어 있지 않다.

 

여기서 아래 특징들을 짚고 넘어가면 좋을 것 같다.

 

1. 특정층 n에 도달하기 위한 비용을 계산할때는 최대 90000만 계산해도 충분히 구할 수 있다.

  land자체는 300*300 작은 크기이기때문에 n층을 맞추기 위해 계산하는것은 시간이 그리 들지 않는다.

 

2. 최소 비용의 층이 m 이라고 생각하면 m보다 작은 층으로 갈 수 록 비용이 증가하고 m보다 큰 층으로 갈수록 비용이 감소한다.

 

이는 문제 조건에서 블록을 빈공간에 둘 수 없다는 규칙때문이다. 고층으로 갈 수록 블록은 적어질수만 있기에 비용 그래프는 웅덩이가 있는 그래프 형식이 된다.

 

아래는 문제 예시의 비용 계산표이다. 최소값인 2를 기준으로 양방향으로 숫자가 점점 커짐을 알 수 있다.

0 층 : 63
1 층 : 44
2 층 : 33
3 층 : 46
4 층 : 75
5 층 : 120
6 층 : 165
7 층 : 210
8 층 : 255
9 층 : 300
10 층 : 345
11 층 : 390
12 층 : 435
13 층 : 480
14 층 : 525
15 층 : 570
16 층 : 615
17 층 : 660
18 층 : 705
19 층 : 750

 

 

즉, 해당 문제는 일종의 "경사하강법"을 따라서 구현해보라는 문제와 비슷하게 되었다.

 

AI에서의 경사하강법

경사하강법을 몰라도 상관은 없다. 위와 같은 형태의 데이터에서 가장 작은 데이터를 구하는 것이다. AI와는 다르게 해당문제에서는 웅덩이가 1개밖에 없으므로 정확한 값을 빠르게 구하기 위해서 이분탐색을 응용해보았다.

 

1. left,right를 0과 최대 층수로 초깃값을 잡아준다.

2. left와 right의 중간의 mid층을 구현할때의 비용을 계산한다.

3. 현재 mid가 왼쪽으로 굴러가야 하는지, 오른쪽으로 굴러가야하는지 상태를 계산해준다. (mid-1,mid+1 의 비용으로 계산)

4. 왼쪽으로 굴러가야 한다면 right=mid-1, 오른쪽으로 굴러가야 한다면 left=mid+1을 반복해서 해주며 웅덩이의 패인 부분을 찾는다.

 

 

 

 

function solution(land, P, Q) {
    // n층일 때 소요되는 비용
  const getCost = (floor) => {
    let ret = 0;
    for (let i = 0; i < land.length; i++) {
      for (let j = 0; j < land[0].length; j++) {
        ret += (land[i][j] - floor) * (land[i][j] > floor ? Q : -P);
      }
    }
    return ret;
  };

  let left = 0;
  let right = Math.max(...land.map((v) => Math.max(...v)));

  //경사하강법과 비슷하게 구현
  while (1) {
    const mid = ~~((left + right) / 2);

    const midCnt = getCost(mid);
    const midLeftCnt = getCost(mid - 1);
    const midRightCnt = getCost(mid + 1);

    //웅덩이에 빠진 경우
    if (midLeftCnt >= midCnt && midRightCnt >= midCnt) return midCnt;

    //현재 내리막길인지 오르막길인지 파악
    if (midLeftCnt < midRightCnt) right = mid - 1;
    else left = mid + 1;
  }
}