[프로그래머스] 최대공약수와 최소공배수

최대공약수와 최소공배수

문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

제한 사항

• 두 수는 1이상 1000000이하의 자연수입니다.

입출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

입출력 예 설명

• 입출력 예 #1
  • 위의 설명과 같습니다.
• 입출력 예 #2
  • 자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

---

나의 풀이

1. n, m 의 약수를 구한다.
2. 두 약수를 비교해서 중복된 값을 filter하고 그 중 가장 큰 수를 index 의 가장 첫번째 자리로 오게 설정해서 최대공약수를 구한다.
3. n * m / 최대공약수 = 최소공배수 식을 활용한다.

function solution(n, m) {
 	let minN = [];
    let minM = [];
    let result = [];
    
  for(let i =1; i<=n; i++) {
        if(n % i === 0) {
          minN.push(i)  
        } 
    }
    
  for(let i=1; i<=m; i++) {
        if(m % i === 0) {
          minM.push(i)  
        } 
    }
  
  // 최대공약수
  const minNum = minN.filter((num) => minM.includes(num)).sort((a,b) => b-a)[0]
  
  // 최소공배수
  const maxNum = n * m / minNum
    
    result.push(minNum, maxNum)
    return result
}

좋다고 생각한 풀이

• n, m 중에 작은 수를 구한다.
• 임의의 변수 한개를 정한다.
• 작은 수를 i 의 값으로 설정하고 i 는 0보다 크고 i가 1씩 줄도록 조건을 준다.
  • 작은 수를 i 의 값으로 설정한 이유는 최대공약수의 가장 큰 수는 작은 수와 큰 수를 비교했을 때 작은 수의 값이기 때문이다.
• n % i 와 m % i 둘 다 0 일때 임의의 수를 i로 바꾸고 if문을 중지한다.
  • 이 조건을 만족하면 최대공약수이다.
• 최대공약수와 최소공배수를 리턴한다.

function solution(n, m) {
    const min = Math.min(n, m);
    let common_max = 1;
  
    for(let i = min; i > 0; i--) {
      // 조건에 맞는 i = 최대공약수
        if(n % i === 0 && m % i === 0) {
            common_max = i;
            break;
        }
    }
  
    return [common_max, n * m / common_max];
}