백준 - 05

10820번 - 문자열 분석

문자열 N개가 주어진다. 이때, 문자열에 포함되어 있는 소문자, 대문자, 숫자, 공백의 개수를 구하는 프로그램을 작성하시오.

각 문자열은 알파벳 소문자, 대문자, 숫자, 공백으로만 이루어져 있다.

---

풀이

const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";

let input = require("fs").readFileSync(filePath).toString().split("\n");

let answer = "";

for (let str of input) {
  // 빈 문자열 입력 받을 시 제외
  if (str == "") continue;
  let arr = [0, 0, 0, 0];

  for (let x of str) {
    if (x == " ") arr[3] += 1;
    // String.match 메서드 활용해 구분
    else if (x.match(/[0-9]/)) arr[2] += 1;
    else if (x.match(/[A-Z]/)) arr[1] += 1;
    else if (x.match(/[a-z]/)) arr[0] += 1;
  }
  answer += arr.join(" ") + "\n";
}

console.log(answer);

---

11655번 - ROT13

ROT13은 카이사르 암호의 일종으로 영어 알파벳을 13글자씩 밀어서 만든다.

ROT13은 알파벳 대문자와 소문자에만 적용할 수 있다.
알파벳이 아닌 글자는 원래 글자 그대로 남아 있어야 한다. 예를 들어, “One is 1”을 ROT13으로 암호화하면 “Bar vf 1”이 된다.

문자열이 주어졌을 때, “ROT13”으로 암호화한 다음 출력하는 프로그램을 작성하시오.

---

풀이

const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";

let input = require("fs").readFileSync(filePath).toString();

// 알파벳을 13칸 밀어야하므로 반복된 문자열을 준비합니다.
let alpha = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz";

let answer = "";

for (let x of input) {
  let word = x;
  // 대문자인 경우 판별용
  let isUpper = false;

  // 알파벳이라면
  if (alpha.includes(x.toLowerCase())) {
    // 대문자라면
    if (x !== x.toLowerCase()) isUpper = true;

    // 입력 문자로 index를 구합니다.
    let index = alpha.indexOf(x.toLowerCase());
    // index에 13을 더해 13칸 밀어줍니다.
    index += 13;

    // 입력 문자가 대문자인지 아닌지를 isUpper 변수로 판별해 word를 갱신합니다.
    word = isUpper ? alpha[index].toUpperCase() : alpha[index];
  }

  answer += word;
}

console.log(answer);

---

최대공약수와 최소공배수

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

---

풀이

유클리드 호제법을 활용합니다.

const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";

let input = require("fs").readFileSync(filePath).toString().trim().split(" ");

let gcd = (a, b) => {
  if (a < b) [a, b] = [b, a];

  return a % b == 0 ? b : gcd(b, a % b);
};

let [a, b] = input;
let answer = [];

answer.push(gcd(a, b));

let lcm = (a * b) / answer[0];

answer.push(lcm);

console.log(answer.join("\n"));

---

1929번 - 소수 구하기

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

---

풀이

m부터 n까지 소수인지 판별합니다.

판별시 시간초과를 막기위해 제곱근까지만 확인합니다.

const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";

let input = require("fs").readFileSync(filePath).toString().trim();

let [m, n] = input.split(" ").map(Number);

let answer = "";

for (let i = m; i <= n; i++) {
  if (isPrime(i)) {
    answer += i + "\n";
  }
}

function isPrime(num) {
  if (num == 1) return false;

  // 제곱근까지만 비교 (시간 줄이기)
  for (let i = 2; i * i <= num; i++) {
    if (num % i == 0) return false;
  }

  return true;
}

console.log(answer);

---

두번째 풀이

시간을 더 줄이기 위해 에라토스테네스의 체를 사용해보자.

임의의 자연수 n보다 작은 소수들은 2부터 제곱근보다 작거나 같은 수까지 소수들의 배수를 지우고 남은 수들과 같습니다.

배열을 만들어 지워나가는 식으로 구현해보겠습니다.

const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";

let input = require("fs").readFileSync(filePath).toString().trim();

let [m, n] = input.split(" ").map(Number);

// 배열은 0부터 시작하므로 +1 해준 크기의 배열 생성
// 값을 인덱스 값으로 변환합니다.
// 1은 소수가 아니므로 0
let primes = new Array(n + 1)
  .fill(0)
  .map((_, index) => (index < 2 ? 0 : index));

// 2부터 n의 제곱근과 같은 수까지 반복문
for (let i = 2; i * i <= n; i++) {
  // 값이 0이 아니면
  if (primes[i]) {
    // 그 값의 배수들을 모두 0으로
    for (let j = i * i; j <= n; j += i) {
      primes[j] = 0;
    }
  }
}

console.log(primes.filter((x) => x >= m && x != 0).join("\n"));

---

6588번 - 골드바흐의 추측

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

---

풀이

입력의 max값으로 에라토스테네스의 체를 활용해 primes 배열을 저장합니다.

find 메서드는 앞에서부터 찾기때문에 a가 가장 작은 b-a가 가장 큰 값을 찾을 수 있습니다.

const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";

let input = require("fs").readFileSync(filePath).toString().trim();

input = input.split("\n").map(Number);
input.pop();

let max = Math.max(...input);

let primes = Array.from(new Array(max), (_, i) => (i > 1 ? i : 0));

setPrimes();

// 입력 num마다 출력을 return해야하므로 map 메서드를 활용합니다.
let answer = input.map((num) => {
  let a = primes.find((a) => primes[num - a]);

  if (a) {
    return `${num} = ${a} + ${num - a}`;
  } else {
    return "Goldbach's conjecture is wrong.";
  }
});

console.log(answer.join("\n"));

function setPrimes() {
  for (let i = 2; i * i <= max; i++) {
    if (primes[i]) {
      for (let j = i * i; j < max; j += i) {
        primes[j] = 0;
      }
    }
  }
}