백준 단계별 - 기본 수학 2

1. 1978번 - 소수 찾기

1. 2의 배수 제외
2. 홀수의 배수중에 홀수의 배수만 제외 ( 3 3 => 제외O, 3 2 => 제외X )
   어차피 2의 배수에서 홀수의 짝수배수는 제외당했기때문에 중복처리하지 않음

/**
 * 입력받은 수 이하의 소수를 구하는 코드를 만들어서 그거에 맞게 조금 변형시킴
 */
const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", line => {
  input.push(line);

  if (input.length >= 2 && input[1].split(" ").length === +input[0]) rl.close();
}).on("close", () => {
  input.shift();
  let targetNumber = 0;

  // 입력한 수중에 제일 큰 수
  targetNumber = input[0].split(" ").reduce((prev, curr) => (prev > +curr ? prev : curr), 0);

  const candidate = Array(+targetNumber)
    .fill()
    .map(() => false);

  // 1제외
  candidate[0] = true;

  // 2의 배수
  for (let i = 4; i <= targetNumber; i += 2) {
    candidate[i - 1] = true;
  }

  // 홀수의 배수 ( 홀수의 배수중에 짝수는 제외 )
  for (let i = 3; i <= targetNumber; i += 2) {
    for (let j = 1; j <= Math.floor(targetNumber / i); j += 2) {
      // 본인 제외
      if (j === 1) continue;

      // 홀수의 배수들 제외 ( 이미 들어간거는 무시 )
      if (!candidate[i * j - 1]) candidate[i * j - 1] = true;
    }
  }

  let count = 0;
  let answer = "";

  input[0].split(" ").forEach(v => (candidate[v - 1] ? null : count++));

  // candidate.forEach((v, i) => (v ? null : (answer += `${i + 1} `)));

  console.log(count);
  // console.log(answer);

  process.exit();
});

2. 2581번 - 소수

/**
 * 입력받은 수 이하의 소수를 구하는 코드를 만들어서 그거에 맞게 조금 변형시킴
 */
const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", line => {
  input.push(+line);

  if (input.length === 2) rl.close();
}).on("close", () => {
  let targetNumber = 0;

  // 입력한 수중에 제일 큰 수
  targetNumber = input[1];

  const candidate = Array(+targetNumber)
    .fill()
    .map(() => false);

  // 1제외
  candidate[0] = true;

  // 2의 배수
  for (let i = 4; i <= targetNumber; i += 2) {
    candidate[i - 1] = true;
  }

  // 홀수의 배수 ( 홀수의 배수중에 짝수는 제외 )
  for (let i = 3; i <= targetNumber; i += 2) {
    for (let j = 1; j <= Math.floor(targetNumber / i); j += 2) {
      // 본인 제외
      if (j === 1) continue;

      // 홀수의 배수들 제외 ( 이미 들어간거는 무시 )
      if (!candidate[i * j - 1]) candidate[i * j - 1] = true;
    }
  }

  let answer = "";
  let sumNumber = 0;
  const numberList = [];

  candidate.forEach((v, i) => {
    if (i + 1 < +input[0]) return;

    if (!v) {
      sumNumber += i + 1;
      numberList.push(i + 1);
    }
  });

  if (sumNumber === 0) answer = -1;
  else answer = `${sumNumber}\n${Math.min(...numberList)}`;

  console.log(answer);

  process.exit();
});

3. 11653번 - 소인수분해

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = null;

rl.on("line", line => {
  input = +line;

  rl.close();
}).on("close", () => {
  const recode = [];
  let n = input;
  let divider = 2;

  // 계속 나누다가 결국 본인을 나누게 되고 그러면 n=1임 즉, 소수가 됨
  while (n != 1) {
    // 나누어 떨어지면
    if (n % divider === 0) {
      recode.push(divider);
      n = n / divider;
    } else {
      divider++;
    }
  }

  let answer = "";
  recode.forEach(v => (answer += `${v}\n`));

  console.log(answer);

  process.exit();
});

4. 1929번 - 소수 구하기

/**
 * 1978번 조금 바꿔서 풀었음
 * 구하지않아도 될 값까지 구해서 조금 비효율적임
 */
const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = null;

rl.on("line", line => {
  input = line.split(" ");

  rl.close();
}).on("close", () => {
  let targetNumber = 0;

  // 입력한 수중에 제일 큰 수
  targetNumber = +input[1];

  const candidate = Array(+targetNumber)
    .fill()
    .map(() => false);

  // 1제외
  candidate[0] = true;

  // 2의 배수
  for (let i = 4; i <= targetNumber; i += 2) {
    candidate[i - 1] = true;
  }

  // 홀수의 배수 ( 홀수의 배수중에 짝수는 제외 )
  for (let i = 3; i <= targetNumber; i += 2) {
    for (let j = 1; j <= Math.floor(targetNumber / i); j += 2) {
      // 본인 제외
      if (j === 1) continue;

      // 홀수의 배수들 제외 ( 이미 들어간거는 무시 )
      if (!candidate[i * j - 1]) candidate[i * j - 1] = true;
    }
  }

  let answer = "";

  candidate.forEach((v, i) => {
    if (i + 1 < +input[0]) return;

    v ? null : (answer += `${i + 1}\n`);
  });
  console.log(answer);

  process.exit();
});

5. 4948번 - 베르트랑 공준

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];
const getPrimeNumber = target => {
  const array = Array(target)
    .fill()
    .map(() => false);

  // 1 제외
  array[0] = true;

  // 2의 배수 제외
  for (let i = 3; i < target; i += 2) {
    array[i] = true;
  }

  // 홀수의 배수들 제외 ( 짝수는 이미 제외했으므로 i += 2 )
  for (let i = 2; i < target; i += 2) {
    // 이미 제외된놈은 연산 X
    if (array[i]) continue;

    // 현재 숫자의 배수 제외 ( 반복은 100에 가까울 때 까지 )
    for (let j = 1; j <= Math.floor(target / (i + 1)); j += 2) {
      // 본인 제외 ( 3, 5, 7, 11 등 )
      if (j === 1) continue;

      // 본인의 배수 제외 ( 9, 15, 21 등... 짝수는 애초에 연산을 안함 )
      array[(i + 1) * j - 1] = true;
    }
  }

  return array;
};

rl.on("line", line => {
  input.push(+line);

  if (input[input.length - 1] === 0) rl.close();
}).on("close", () => {
  input.pop();

  // 입력한 수중에 최댓값 구하기
  const max = input.reduce((prev, curr) => (prev > curr ? prev : curr));

  // 소수 구하기 ( false가 소수, array[0]이 숫자 1 )
  const primeNumberList = getPrimeNumber(max * 2);

  // 정답 기록
  let answer = "";
  input.forEach(n => {
    let count = 0;
    for (let i = n + 1; i <= n * 2; i++) {
      if (!primeNumberList[i - 1]) count++;
    }

    answer += `${count}\n`;
  });

  console.log(answer);

  process.exit();
});

6. 9020번 - 골드바흐의 추측

/**
 * let targetNumber = 입력받은 수 / 2;  // 짝수니까
 * (targetNumber - 1)과 (targetNumber + 1)이 모두 소수인지 확인을 반복
 */
const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];
const getPrimeNumber = target => {
  const array = Array(target)
    .fill()
    .map(() => false);

  // 1 제외
  array[0] = true;

  // 2의 배수 제외
  for (let i = 3; i < target; i += 2) {
    array[i] = true;
  }

  // 홀수의 배수들 제외 ( 짝수는 이미 제외했으므로 i += 2 )
  for (let i = 2; i < target; i += 2) {
    // 이미 제외된놈은 연산 X
    if (array[i]) continue;

    // 현재 숫자의 배수 제외 ( 반복은 100에 가까울 때 까지 )
    for (let j = 1; j <= Math.floor(target / (i + 1)); j += 2) {
      // 본인 제외 ( 3, 5, 7, 11 등 )
      if (j === 1) continue;

      // 본인의 배수 제외 ( 9, 15, 21 등... 짝수는 애초에 연산을 안함 )
      array[(i + 1) * j - 1] = true;
    }
  }

  return array;
};

rl.on("line", line => {
  input.push(+line);

  if (input.length >= 2 && input.length - 1 === +input[0]) rl.close();
}).on("close", () => {
  input.shift();

  // 입력한 수중에 최댓값 구하기
  const max = input.reduce((prev, curr) => (prev > curr ? prev : curr));

  // 소수 구하기 ( false가 소수, array[0]이 숫자 1 )
  const primeNumberList = getPrimeNumber(max);

  // 정답 기록
  let answer = "";
  input.forEach(n => {
    // 짝수라서 /2
    // +1, -1은 while문 제일 앞에 += 1, -=1 적기 위해서임 ( 이게 더 보기 좋아서 )
    let biggerNumber = n / 2 - 1;
    let smallerNumber = n / 2 + 1;
    let condition = true;

    while (condition) {
      biggerNumber += 1;
      smallerNumber -= 1;

      if (!primeNumberList[biggerNumber - 1] && !primeNumberList[smallerNumber - 1]) {
        answer += `${smallerNumber} ${biggerNumber}\n`;
        condition = false;
      }
    }
  });
  console.log(answer);

  process.exit();
});

7. 1085번 - 직사각형에서 탈출

/**
 * let targetNumber = 입력받은 수 / 2;  // 짝수니까
 * (targetNumber - 1)과 (targetNumber + 1)이 모두 소수인지 확인을 반복
 */
const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = null;

rl.on("line", line => {
  input = line.split(" ");

  rl.close();
}).on("close", () => {
  // 정수로 변환
  input = input.map(v => +v);

  const x = input[0];
  const y = input[1];
  const w = input[2];
  const h = input[3];

  // 정답 기록
  let answer = "";

  answer = Math.min(x, y, w - x, h - y);

  console.log(answer);

  process.exit();
});

8. 3009번 - 네 번째 점

/**
 * 같은 X값 필연적으로 존재, 남은 X값은 두개가 같음
 * Y값도 이하동문
 */

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", line => {
  input.push(line.split(" "));

  if (input.length === 3) rl.close();
}).on("close", () => {
  const point1 = input[0].map(v => +v);
  const point2 = input[1].map(v => +v);
  const point3 = input[2].map(v => +v);
  let x = 0;
  let y = 0;

  // x구하기
  if (point1[0] === point2[0]) x = point3[0];
  else if (point2[0] === point3[0]) x = point1[0];
  else x = point2[0];

  // y구하기
  if (point1[1] === point2[1]) y = point3[1];
  else if (point2[1] === point3[1]) y = point1[1];
  else y = point2[1];

  // 정답 기록
  let answer = `${x} ${y}`;

  console.log(answer);

  process.exit();
});

9. 4153번 - 직각삼각형

/**
 * "제일큰수 ** 2 === 남은수1 ** 2 + 남은수2 ** 2"에 만족하면 직각삼각형
 */

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", line => {
  input.push(line);

  if (input[input.length - 1] === "0 0 0") rl.close();
}).on("close", () => {
  input.pop();

  // 정답 기록
  let answer = "";

  input.forEach(value => {
    let candidate = value.split(" ");
    candidate = candidate.map(v => +v);

    // 제일 큰 수 구하고
    let biggerLine = Math.max(...candidate);

    // 제일 큰 수 배열에서 제외하고
    candidate.splice(candidate.indexOf(biggerLine), 1);

    let biggerLineOfSqared = biggerLine ** 2;
    let otherLineOfSqaredSum = candidate.reduce((prev, curr) => prev ** 2 + curr ** 2);

    if (biggerLineOfSqared === otherLineOfSqaredSum) {
      answer += `right\n`;
    } else {
      answer += `wrong\n`;
    }
  });

  console.log(answer);

  process.exit();
});

10. 3053번 - 택시 기하학

/**
 * 원의 정의는 중점에서 거리가 같은 점의 집합인데
 * 택시기하학에서는 거리를 좌표평면의 하나의 라인으로 취급함 ( 이거는 구글에 검색해서 그림을 보는 것이 이해가 쉬움 )
 * 택시기하학에서는 원을 그리면 마름모형태가 나오고
 * 마름모의 넓이는 두개의 삼각형으로 나눠서 생각하면
 * 삼각형 넓이 = 2R * R * 1/2 = R ** 2
 * 마름모 넓이 = (R ** 2) * 2
 */

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = null;

rl.on("line", line => {
  input = +line;

  rl.close();
}).on("close", () => {
  // 정답 기록
  let answer = "";

  answer += `${Math.PI * input ** 2}\n`;
  answer += `${2 * input ** 2}`;

  console.log(answer);

  process.exit();
});

11. 1002번 - 터렛

/**
 * "터렛의 위치 = 원의 중점"으로 생각하고 풀면 된다.
 * 결국 경우의 수를 따지는 문제임 ( 처음에 문제 이해를 잘못함; )
 * 터렛이 원이라고 가정했을 때
 * 두 개의 터렛과 마린과의 각각의 거리를 따져서
 * 1. 두 개의 원이 외부에서 접하지 않음
 * 2. 두 개의 원이 내부에서 접하지 않음
 * 3. 두 개의 원이 외접함
 * 4. 두 개의 원이 내접함
 * 5. 두 개의 원이 두 점에서 만남
 * 6. 두 개의 원이 동일한 원임
 * 위 6가지 경우의 수를 따지면 됨
 */

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", line => {
  input.push(line);

  if (input.length >= 2 && input.length - 1 === +input[0]) rl.close();
}).on("close", () => {
  input.shift();

  // 각 배열로 분리 후 숫자로 변환
  input = input.map(value => value.split(" ").map(v => +v));

  // 정답 기록
  let answer = "";

  input.forEach(value => {
    const x = [value[0], value[3]];
    const y = [value[1], value[4]];
    const r = [value[2], value[5]];
    const distance = Math.sqrt((x[0] - x[1]) ** 2 + (y[0] - y[1]) ** 2);

    // 같은 원
    if (x[0] === x[1] && y[0] === y[1] && r[0] === r[1]) {
      answer += -1 + "\n";
    }
    // 외부에서 접하지 않음 or 내부에서 접하지 않음
    else if (distance > r[0] + r[1] || distance < Math.abs(r[0] - r[1])) {
      answer += 0 + "\n";
    }
    // 외접 or 내접
    else if (distance === r[0] + r[1] || distance === Math.abs(r[0] - r[1])) {
      answer += 1 + "\n";
    }
    // 두 점
    else if (distance < r[0] + r[1] && distance > Math.abs(r[0] - r[1])) {
      answer += 2 + "\n";
    }
  });

  console.log(answer);

  process.exit();
});

0. 마무리

이번에 소수를 구하는 문제가 많았는데 처음에 이론으로 생각했을 때는 별로 어렵지 않다고 생각했고, 실제로 코드만 보면 그렇게 어렵지 않은 코드다.
그런데 헷갈리는게 너무 많아서 힘들었다. 인덱스는 0부터인데 숫자는 1부터라서 이 간극을 메우는게 이미 적응을 해서 상관없을줄 알았는데 에라토스테네스의 체를 구현할 때 배수를 제외시켜줘야하는데 곱하기를 무작정 해버리면 실제로는 3*2를 해야하는데 코드상으로 2*2가 되어버려서 다른 숫자를 비소수로 만들어버리는 경우 등의 실수를 너무 많이 했다.