[백준/BOJ] 1934번 최소공배수 (Javascript / Node js)

https://www.acmicpc.net/problem/1934

1934번: 최소공배수

문제 해석

문제 자체는 명확하고 간단하다. 테스트 케이스 각각의 두 수(A, B)의 최소 공배수를 출력해주면 된다.

 

부끄럽지만 나는 이 문제를 풀기전까지 유클리드 호제법에 대해 아는 것이 없었다. 최대공약수로 최소공배수를 구할 수 있다는 사실조차 어렴풋이 중고등학교 시절에 배운 기억이 있지만 기억이 났던건 문제를 다 풀고 난 후였다.

 

그래서 내가 생각해낸 풀이 방식은,,

 

입력 받은 A 와 B를 소인수로 전부 쪼갠다.

 

ex) 6 => 2 * 3,  20 => 2 * 2 * 5

 

그리고 쪼갠 소인수들로 소인수를 key, 소인수의 개수를 value로 갖는 Map객체를 생성한다.(key를 정수로 받기 위해 Object가 아닌 Map을 사용해야 한다.) 

 

ex) 6 = { 2 : 1 , 3 : 1 } , 20 = { 2 : 2 , 5 : 1 }

 

이렇게 생성된 두 객체를 집합이라 생각하고 두 집합의 합집합이 최소공배수가 된다는게 내 생각이였다. 

{ 2 : 1, 3 : 1 } 과 { 2 : 2 , 5 : 1} 의 합집합 => { 2 : 2 , 3 : 1, 5 : 1} => 2 * 2 * 3 * 5 = 60

이걸 합집합이라고 불러도 될 지는 모르겠지만 이것을 합집합이란 단어보다 잘 어울릴 설명이 떠오르지 않아서 두 객체를 합치는 것을 합집합으로 비약했다.

 

이제 위 알고리즘을 코드로 구현하면 아래와 같이 나온다.

 

전체코드 (1)

const input = require("fs")

  .readFileSync("../input.txt")

  .toString()

  .trim()

  .split("\n")

  .map((item) => item.split(" "));

const arr = input.map((item) => item.map((item) => Number(item)));

arr.shift();

var answer = [];

for (let i = 0; i < arr.length; i++) {

  let A = arr[i][0];

  let B = arr[i][1];

  if (A == 1 || B == 1) {

    answer.push(A * B);

    continue;

  }

  let measuresA = new Map([]); // A를 소인수들로만 쪼갠값들을 담을 객체 

  let measuresB = new Map([]); // B를 소인수들로만 쪼갠값들을 담을 객체

  let measuresAB = new Map([]); // 최대 공배수의 소인수들을 담을 객체

  let num = 2;

  while (A != 1) {

    if (A % num == 0) {

      A = A / num;

      if (measuresA.has(num)) {

        measuresA.set(num, measuresA.get(num) + 1);

      } else {

        measuresA.set(num, 1);

      }

    } else {

      num++;

    }

  }

  num = 2;

  while (B != 1) {

    if (B % num == 0) {

      B = B / num;

      if (measuresB.has(num)) {

        measuresB.set(num, measuresB.get(num) + 1);

      } else {

        measuresB.set(num, 1);

      }

    } else {

      num++;

    }

  }

  measuresA.forEach((value, key, map) => {

    measuresAB.set(key, value);

  });

  measuresB.forEach((value, key, map) => {

    if (measuresAB.has(key) && measuresAB.get(key) < value) {

      measuresAB.set(key, value);

    }

   

    if(!measuresAB.has(key)){

      measuresAB.set(key, value);

    }

  });

  let sum = 1;

  measuresAB.forEach((value, key, map) => {

    sum = sum * Math.pow(key, value);

  });

  answer.push(sum);

}

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

 

당연히 위처럼 풀면 굉장히 비효율적이고 처리시간도 오래걸린다. 그래서 출제자가 원한 풀이방법이 아닌 내가 억지로 짜낸 코드라는 생각이 들어 풀이방법을 검색해봤고, 유클리드 호제법과 최대공약수로 최대공배수를 구하는 방법을 알게됐다.

 

유클리드 호제법에 대해서는 내가 설명하는 건 의미가 없다고 생각하여 아래에 링크를 참조하는 것으로 간추리겠다.

 

유클리드 호제법 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

아래는 유클리드 호제법을 이용해 최대공약수를 구하고, 구한 최대공약수를 이용해 최대공배수를 구하는 전체코드이다.

전체코드(2)

const input = require("fs")

  .readFileSync("/dev/stdin")

  .toString()

  .trim()

  .split("\n")

  .map((item) => item.split(" "));

const arr = input.map((item) => item.map((item) => Number(item)));

arr.shift();

var answer = [];

for (let i = 0; i < arr.length; i++) {

  let big = arr[i][0] > arr[i][1] ? arr[i][0] : arr[i][1];

  let small = arr[i][0] < arr[i][1] ? arr[i][0] : arr[i][1];

  let bigMSmall = big * small;

  let mod = big % small;

  let tmp = 0;

  while(mod != 0){

    tmp = mod;

    mod = small % mod;

    small = tmp;

  }

  let GCD = small;

  answer.push(bigMSmall / GCD);

}

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

 

아래는 유클리도 호제법을 사용했을 때와 내가 짠 코드의 처리시간 차이이다. 

내가 짠 코드

유클리드 호제법

 

그래도 마구잡이로 구현하며 Map 객체의 내장 foreach함수를 사용하는 법을 배워 나름의 성취도 얻을 수 있었다. ㅎㅎ