[코딩테스트]프로그래머스 - N개의 최소공배수

Adela·2020년 5월 25일
0

프로그래머스

목록 보기
22/30
post-thumbnail

N개의 최소공배수

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한 사항

  • arr은 길이 1이상, 15이하인 배열입니다.
  • arr의 원소는 100 이하인 자연수입니다.

입출력 예

arr		result
[2,6,8,14]	168
[1,2,3]		6

해결한 코드

function solution(arr) {
  var answer = 0
  var i = 1
  arr = arr.sort((a,b)=>a-b)
  while(true){
    var ptr = arr[arr.length-1]
    var result = [] 
    for(var j=0; j<arr.length; j++){
      result.push((ptr*i)%arr[j])
    }
    if(result.every(e=> e===0){
       answer = ptr*i
       break
    } else {
      i++
    }
  }
  return answer
}

알고리즘

  1. arr의 가장 큰 수를 뽑는다.
  2. 1부터 곱해나가며 arr안의 수와 배수관계가 되면 그 수가 최소공배수가 된다.
    2-1. 1,2,3, ... 을 계속 곱해나간다.
    2-2. arr의 원소들과 나누어 나머지가 모두 0이 되면 그 수는 모든 arr 원소와 배수이면서 최소공배수가 된다.
  3. 이 수를 answer에 담아 return 한다.

또 한번 단순하게 생각하는 사고를 가질 필요성을 느낀 문제.
무식해보여도, 또 생각해보면 이런 무식한 방법을 컴퓨터가 사용하지 누가 사용하겠냐 싶기는 함 ㅋㅋㅋㅋ
나는 어떻게 최소공배수를 구할까, 유클리드 호제법처럼 뭘 또 사용해야 하나 그런 궁리만 했었다 .. ^_ㅠ

profile
개발 공부하는 심리학도

0개의 댓글