TIL 88 | 프로그래머스 카펫 (JS) 이진탐색

문제

https://programmers.co.kr/learn/courses/30/lessons/42842?language=javascript

접근

yellow칸 개수와 brown칸 개수의 관계
// yellow의 가로 길이 2 = 모서리를 제외한 상하 brown칸의 개수
// yellow의 세로 길이 2 = 모서리를 제외한 좌우 brown칸의 개수
// 마지막에 모서리의 개수 4를 더해준다.

발견한 규칙
// 가로로 길어질 때는 노란색이 1개당 갈색이 2개씩 증가
// 세로로 길어질 때는 노란색이 2배씩 증가할 때 갈색이 2개씩 증가

문제 해결 키
yellow칸의 가로 세로 비율에 따라 brown칸이 달라지므로
이진탐색과 같이 높이 값에

제약 조건
카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 길다.

• 제약조건을 고려하면 카펫의 최대 높이는 yellow 개수 제곱근의 정수라는 것을 알 수 있다.

코드

1차 : 최대 높이부터 대입하여 높이를 한 칸씩 낮춰가며 답을 찾아내는 방법

function solution(brown, yellow) {
  let answer;
  let height = Math.floor(Math.sqrt(yellow));
  
  while (true) {
      let cntBrown = (yellow/height+height)*2+4;
      if (cntBrown=== brown) {
          answer = [yellow/height+2, height+2];
          return answer;
      } else {
          height--;
      }
  };

  return answer;
}

2차 : 이진탐색을 이용

function solution(brown, yellow) {
    let maxHeight = Math.floor(Math.sqrt(yellow));
    let height = maxHeight/2;
    let low = 1;
    let answer;
    
    
    while (height <= maxHeight) {
        let cntBrown = (yellow/height+height)*2+4;
        if (cntBrown=== brown) {
            answer = [yellow/height+2, height+2];
            return answer;
        } else if (cntBrown > brown) {
            low = height + 1;
            height = Math.floor((maxHeight + low)/2);
        } else {
            maxHeight = height - 1;
            height = Math.floor((maxHeight + low)/2)
        }
    }
    
    return answer;
}