[Lv1] 최대공약수와 최소공배수

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

 

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, 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]을 리턴해야 합니다.

 

---

두 수 이므로 쉬움.

 

int low = Math.min(n, m);
int high = Math.max(n, m);
if(low==high) return new int[] {n,n};

우선 두 수 중 작은 수(low)와 큰 수(high)를 구분하고,

 

혹시 같다면 최소공배수와 최대공약수는 자신이므로 자신을 두 번 넣어 반환.

 

 

int[] answer = new int[2];
PriorityQueue<Integer> que = new PriorityQueue<>(Collections.reverseOrder());
for(int i=low;i>=1;i--) {
    if(low%i==0) que.add(i);
}
while(true) {
    int now = que.poll();
    if(high%now==0) {
        answer[0] = now;
        break;
    }
}

최대공약수부터.

 

내림차순(큰 것이 먼저)으로 정리되는 우선순위 큐에

 

low의 약수들(low를 나눌 때 나머지를 0으로 만들 수 있는)을 넣어준다.

 

그 후, 큐에서 꺼내면서(큰 것부터 꺼내진다.) 그 수가 high도 나머지를 0으로 나눌 수 있다면 최대공약수.

 

 

int increase = 0;
while(true) {
	increase++;
	for(int i = increase; low * i <= high * increase; ++i) {
		if(low * i == high * increase) {
			answer[1] = low * i;
			return answer;
		}
	}
}

이어서 최소공배수.

 

while 전에 increase를 0으로 잡아,

 

while에서 처음에 1로 시작하여 루프마다 1씩 증가되게 한다.

 

increase는 high의 이번 배수에 관여한다.

 

즉 처음엔 high, 그 다음 루프엔 high*2, 그 다음 루프엔 high*3, ...

 

이 때, low*i는 이 high*increase와 비교하는데, low의 배수들이 현재 high의 배수 이하일 때 까지만 i를 증가시킴.

 

그러다 low*i와 이번 루프 high의 배수가 값이 일치하면, 그 값이 최소공배수.