프로그래머스(programmers) - 최대공약수와 최소공배수(코딩테스트 연습)

최대공약수와 최소공배수

 

풀이

function solution(n, m) {
  var answer = [];
  let a = n;
  let b = m;
  let x;
  // 두 수가 같은경우
  if (n === m) {
    return [n, m];
  }
  // 최대공약수
  if (n > m) {
    while (m > 0) {
      let temp = m;
      m = n % m;
      n = temp;
    }
    answer.push(n);
    //최소공배수
    let x = (a * b) / n;
    answer.push(x);
  } else if (m > n) {
    while (n > 0) {
      let temp = n;
      n = m % n;
      m = temp;
    }
    answer.push(m);
    //최소공배수
    let x = (a * b) / m;
    answer.push(x);
  }
  return answer;
}

최대공약수를 구하는 방법이 몇가지 있는데 그중 이해만 한다면 간단하게 사용할 수 있는 '유클리드 호제법'이 있다.

'유클리드 호제법'이란 나눗셈만 반복해서 최대공약수를 구할 수 있는 알고리즘인데,

예를들어, 0보다 큰 두개의 자연수 a, b가 각각 6 과 4 라고 하면  b(여기서 말하는 b는 a를 b로 나눈 나머지)가 0 보다 크면 계속해서 나눗셈을 반복시키고 a를 b로 나눴을때 나머지가 0이 나오는 때의 a 값이 최대공약수가 되는것이다.

 

1. a = 6, b = 4 라면 나머지가 2 이고 그 다음엔 a = 4, b= 2가 된다.

2. a = 4, b = 2 라면 나머지가 0 이고 a = 2, b = 0 이므로 

이 두 자연수의 최대공약수는 2가 되는것이다.

 

여기서는 어떠한 조건이 충족되는 이상 계속 루프문을 돌려주기 위해 while문을 사용하였다.

그 후 answer.push()를 통해 리턴값에 저장을 해준다.

 

최소공배수를 구하는 방법도 여러가지가 있지만 가장 쉬운 방법은 최대공약수와의 관계를 이용하는 것이다. 

'최소공배수 = 0보다 큰 두 수의 곱 / 두 수의 최대공약수' 라는 공식을 이용하면 

위와같이 쉽게 최소공배수도 구할 수 있다.

위에서 최대공약수를 구할 때 자연수 m 과 n 값을 바꿔주기 때문에 반복문이 돌기 전 미리 m, n 값을 각각 a, b에 저장해준 뒤 미리 선언해 둔 x에 담아 answer 배열에 다시 넣어줌으로써 원하는 [최대공약수, 최소공배수]의 리턴값을 얻을 수 있다.

 

그리고 두 수가 같은 경우에는 최대공약수와 최소공배수가 같기 때문에 조건문을 사용해 먼저 위에서 걸러주었다.

(반복문 밑에 저 조건을 넣어주면 불필요하게 반복문이 작동하기 때문에 효율성이 안좋을 것이라 예상한다) 

 

 

다른 사람의 풀이중 정말 감탄한 코드가 있어 추가로 작성해본다.

function solution(a, b) {
	let x;
    for(let ab = a * b; r = a % b; a = b, b = r){}
    return [b, ab/b];
}

진짜 너무 소름돋았다. 

처음 저 코드를 봤을때 이해가 안가 for문을 몇개월 만에 다시 구글링을 해보았다.

저 코드로 실행 해봤을때 ab가 선언이 안되어있어서 let x; 밑에 let ab를 선언해줬는데도

사실상 문제가 바뀌어서 그런지 아니면 코드가 완벽하지 않은건지는 모르겠지만 잘 작동하진 않았다.

하지만 내가 소름이 돋았던 부분은 저 코드 자체가 아닌 for문에 대해 좀 더 자세히 알게돼서 이다.

for (초기식; 조건식; 증감식) {
	조건식의 결과가 참인 동안 반복적으로 실행하고자 하는 실행문;
}

for문은 위와 같은데 구성하는 초기식, 조건식, 증감식은 각각 생략될 수 있으며 쉼표 연산자(,)를 사용하면 여러 개의 초기식이나 증감식을 동시에 사용할 수도 있다.

그렇다는것은 여기서 ab라는것은 a * b 라고 초기식에서 선언을 해주고,

조건식이 참이라면 저 반복문은 계속 실행이 되기 때문에 r이 0이 나오면 false가 반환되어 반복문이 멈추기 때문에 0이 나올때까지 나누기가 반복되도록 조건식에 넣어주었고, 

마지막으로 쉼표 연산자를 사용하여 증감식(다음 for문이 바뀔때 적용이 될 부분, 보통의 for문에선 i++처럼 증가 시킴)에 a = b, b = r 이라는 증감식을 넣어주어 '유클리드 호제법'을 완성시켰다.

 

나는 그저 이때까지 for문을 for(let i = 0; i < arr.length; i++){}와 같이 사용해왔는데 정말 다양한 방법으로 for문을 쓸 수 있다는 것을 알게되었다.

 

이 문제를 통해 정해진 틀에 갇히지 말고 그 틀을 깰 수 있는 사고를 하고싶다고, 어떠한 것을 바라볼 때 다양한 관점에서 바라보고 싶다고 느껴졌다.