Programming Challenges #35

 

문제 : 과거 지구에 외계 문명이 존재했다는 것을 밝혀줄 증거를 찾고 있는 고고학자가 이상한 숫자가 한 줄로 나열되어있는, 부쉬진 벽을 발견했다. 이 숫자들이 왼쪽 부분은 상태가 아주 양호해서 숫자가 잘 보이지만 안타깝게도 오른쪽 부분에 있는 숫자들은 풍화로 인해 잘 안 보이는 것이 많다. 그 고고학자는 잘 보이는 숫자는 모두 2의 거듭제곱이라는 것을 발견하고는 모든 숫자들이 2의 거듭제곱이라는 가설을 세웠다. 그녀는 이 가설을 뒷받침하기 위해 잘 보이는 숫자의 개수가 잘 보이지 않는 숫자의 갯수보다 적은 숫자들을 목록으로 정리했다. 그리고는 당신에게 목록에 있는 것과 같은 첫번째 자리의 숫자를 가지는 가장 작은 2의 거듭제곱을 찾아 달라고 부탁했다. 어떤 정수가 주어졌을때 2^E의 첫째 자리 숫자(맨 왼쪽에 있는 숫자)가 그 정수와 같게 되는 가장 작은 지수 E를 결정하는 프로그램을 만들어라(숫자 가운데 절반 이상은 보이지 않는다.)

const STORE_NUM = 70777;

function binarySearch(direction, type) {
  let search_left = 0;
  let search_right = STORE_NUM - 1;
  while (search_left <= search_right) {
    const mid = Math.floor((search_left + search_right) / 2);
    if (direction < log2_house[mid].value) {
      search_right = mid - 1;
    } else {
      search_left = mid + 1;
    }
  }
  if (type == 1) {
    return search_left  
  }else{
    return search_right
  }
}

function findCandidate(left, right, poss_min, now_min) {

  left -= 0.00000000000001;
  right += 0.00000000000001;

  let left_limit = binarySearch(left, 1);
  let right_limit = binarySearch(right, 0);

  for (let i = left_limit; i <= right_limit; i++) {
    if (log2_house[i].mult >= poss_min && (now_min === -1 || log2_house[i].mult < now_min)) {
      now_min = log2_house[i].mult;
    }
  }

  return now_min;

}

let log2_house = new Array(STORE_NUM).fill(null);

log2_house = log2_house.reduce((ac, e, i, array) => {
  e = {};
  e['value'] = (Math.log10(2.0) * i) - Math.floor(Math.log10(2.0) * i);
  e['mult'] = i;
  ac.push(e)
  return ac;
}, []).sort((type1, type2) => {
  const t1 = type1;
  const t2 = type2;
  const diff = t1.value - t2.value;
  if (diff < 0) {
    return -1;
  } else if (diff > 0) {
    return 1;
  } else {
    return 0;
  }
});

function calculator(n) {

  let now_check = 0;
  let min_candidate;
  let left, right;

  left = Math.log10(n);
  left -= Math.floor(left);
  right = Math.log10(n + 1);
  right -= Math.floor(right);

  if (left > right) {
    right += 1.0;
  }      

  min_candidate = Math.floor(Math.log10(n)) + 1;
  min_candidate = min_candidate * 2;
  min_candidate = Math.floor(min_candidate / Math.log10(2) + 0.99999999);


  let answer = -1;

  while (answer < 0) {

    let base = now_check * Math.log10(2);
    base = 1 - base;

    if (left + base >= 1.0) {
      answer = findCandidate(left + base - 1.0, right + base - 1.0, min_candidate - now_check, answer);
    } else if (right + base >= 1.0) {
      answer = findCandidate(left + base, 1.0, min_candidate - now_check, answer);
      answer = findCandidate(0.0, right + base - 1.0, min_candidate - now_check, answer);
    } else {
      answer = findCandidate(left + base, right + base, min_candidate - now_check, answer);
    }

    now_check += STORE_NUM;

  }

  console.log(`===> answer: ${answer}`);

}

calculator(1)
calculator(2)
calculator(10)

설명 : 

해당 코드는 주어진 숫자 n에 대해 2의 지수값을 찾는 프로그램입니다. 주요 기능은 다음과 같습니다. 기본적으로 '상용로그'에 대한 개념을 이해하고 접근해야 합니다.

1. const STORE_NUM = 70777;: 상수 STORE_NUM을 70777로 정의합니다.
2. function binarySearch(direction, type) { ... }: binarySearch 함수는 이진 탐색을 수행하여 direction에 따른 type에 따라 left or right 값을 리턴합니다. 해당 값은 이진탐색에서 left or right값에 원하는 타겟을 리턴하기 위한 함수입니다.
3. function findCandidate(left, right, poss_min, now_min) { ... }: findCandidate 함수는 주어진 범위 내에서 조건을 만족하는 최솟값을 찾는 역할을 합니다. left와 right는 탐색할 범위를, poss_min은 최소 가능한 값을, now_min은 현재까지의 최솟값을 나타냅니다. 함수 내부에서는 binarySearch 함수를 이용하여 left와 right 값이 위치해야 할 인덱스를 찾습니다. 그리고 해당 인덱스 범위 내에서 조건을 만족하는 최솟값을 찾아 now_min 값을 업데이트하고 반환합니다.
4. let log2_house = new Array(STORE_NUM).fill(null);: log2_house라는 배열을 생성하고, 초기값을 null로 채웁니다. 이 배열은 STORE_NUM 개의 요소를 가지며, 나중에 객체들로 채워질 것입니다.
5. log2_house = log2_house.reduce((ac, e, i, array) => { ... });: reduce 메서드를 사용하여 log2_house 배열을 초기화합니다. 각 요소마다 객체를 생성하고, value와 mult 속성을 할당합니다. 이때, Math.log10(2.0) * i 값을 이용하여 value를 계산하고, mult는 현재 인덱스 i로 설정합니다. 객체를 생성한 후 ac 배열에 추가하고 반환합니다.
6. log2_house = log2_house.sort((type1, type2) => { ... });: log2_house 배열을 sort 메서드를 사용하여 정렬합니다. type1과 type2를 비교하는 함수를 사용하여 오름차순으로 정렬됩니다.
7. function calculator(n) { ... }: calculator 함수는 주어진 숫자 n에 대한 계산을 수행하는 함수입니다. now_check, min_candidate, left, right, answer 변수들을 초기화합니다.
8. while (answer < 0) { ... }: answer 값이 0 미만인 동안 반복합니다. 이는 조건을 만족하는 최솟값을 찾을 때까지 반복하는 것을 의미합니다.
9. let base = now_check * Math.log10(2); base = 1 - base;: base 변수에 현재 now_check 값을 이용하여 계산된 값을 할당합니다. 이는 범위 계산을 위해 사용됩니다.
10. 조건에 따라 findCandidate 함수를 호출하여 최솟값을 찾습니다. left + base >= 1.0인 경우에는 left + base - 1.0와 right + base - 1.0 범위에서 최솟값을 탐색합니다. right + base >= 1.0인 경우에는 left + base와 1.0 범위, 그리고 0.0와 right + base - 1.0 범위에서 최솟값을 탐색합니다. 그렇지 않은 경우에는 left + base와 right + base 범위에서 최솟값을 탐색합니다. 이때, min_candidate - now_check는 가능한 최솟값의 개수를 나타내는 값입니다. 찾은 최솟값은 answer 변수에 저장됩니다.
11. 반복문이 종료된 후, 최종 결과인 answer 값을 출력합니다.
12. calculator(1); calculator(2); calculator(10);: calculator 함수를 각각 1, 2, 10의 인자로 호출하여 실행합니다. 이를 통해 각각의 경우에 대한 계산 결과를 출력합니다.

주어진 코드는 calculator 함수를 세 번 호출하여 각각 n 값이 1, 2, 10일 때의 결과를 출력하는 예시입니다. n 값에 따라서 계산을 수행하고, 조건에 따라 최솟값을 찾아 출력합니다.