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

문제 설명

 

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

 

 

제한 조건

 

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

 

---

풀이 과정 (자바)

 

기존에 int형 배열을 반환하게 되어 있었으나 입력받는 수가 1000000, 999999인 경우, int형 범위가 넘어가 버려 long 형으로 변경했다.

 

answer[0]에는 최대공약수, answer[1]에는 최소공배수 값을 넣었다.

입력받는 수는 1이상 1000000이하의 자연수를 받는다고 되어있다.

2부터 1000000까지 for문을 돌려 두 수가 나뉘면 그 나뉜 값을 answer[0]에 곱했다.

그리고 다시 처음부터 다시 for문을 돌려 나뉘는 확인했다.

for문이 끝날 때까지 나뉘지 않으면 더는 계산되지 않는다고 판단하고, answer[1]에 최소공배수 값을 넣었다.

 

 

결과

 

 

---

다른 사람의 풀이

 

유클리드 호제법을 이용해 처리했다.

 

answer[0]에는 최대공약수, answer[1]에는 최소공배수 값을 넣었다.

gcd라는 메서드를 하나 만들어 값을 받아 처리했다.

 

여기서, q라는 것은 두 수를 나눴을 때의 나머지다.

나머지가 0이라는 것은 나머지 없이 원하는 값으로 나뉘었다는 것을 의미한다.

또한 이는 두 수의 최대공약수를 뜻한다.

 

그래서 최대공약수가 나올 때까지 (나머지 0, 여기서는 q가 0이 될 때) 계속해서 계산했다.

그리고 최대공약수가 나오면 이를 통해 최소공배수를 구했다.

최소공배수는 두 수의 곱에서 최대공약수로 나눠준 값이다.

예를 들어, 2이랑 5를 입력받았다고 하면,

처음에 p: 2, q: 5다.

q가 0이 아니므로 gcd(5, 2%5)를 실행한다.

2%5: 2라는 결과가 나온다.

 

그러면 gcd(5, 2)는 p: 5, q: 2이 된다.

q가 0이 아니므로 gcd(2, 5%2)를 실행한다.

5%2: 1이라는 결과가 나온다.

 

그러면 gcd(2, 1)는 p: 2, q: 1이 된다.

q가 0이 아니므로 gcd(1, 2%1)를 실행한다.

2%1: 0이라는 결과가 나온다.

 

그러면 gcd(1, 0)는 p: 1, q: 0이 된다.

q가 0이므로 p: 1을 반환한다.

 

두 수의 최대공약수는 1이다.

그리고 최소공배수는 두 수의 곱/최대공약수 (2 * 5 / 1 = 10) 10이다.

 

 

기타

 

유클리드 호제법을 통해 간략하게 처리하는 방법을 알게 되었다.

for문을 돌리는 것은 1 ~ 1000000까지의 수에 대해서 전부 나눠서 확인해 봐야 하지만 유클리드 호제법을 이용해 처리하게 되면 입력받은 수에 대해서만 처리를 진행하면 되므로, 속도도 굉장히 빠르게 처리할 수 있었다.

아는 것이 힘이 맞는 거 같다. 효율적으로 처리하기 위해서는 많이 배워야겠다.