🗣️ 메모
최대공약수 니가 몬데 날 힘들게 해,,
✏️ [분수의 덧셈, 최대공약수 활용]
문제 설명
첫 번째 분수의 분자와 분모를 뜻하는 denum1, num1, 두 번째 분수의 분자와 분모를 뜻하는 denum2, num2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.
제한사항
- 0 <denum1, num1, denum2, num2 < 1,000
입출력 예
denum1 | num1 | denum2 | num2 | result |
1 | 2 | 3 | 4 | [5, 4] |
9 | 2 | 1 | 3 | [29, 6] |
입출력 예 설명
입출력 예 #1
- 1 / 2 + 3 / 4 = 5 / 4입니다. 따라서 [5, 4]를 return 합니다.
입출력 예 #2
- 9 / 2 + 1 / 3 = 29 / 6입니다. 따라서 [29, 6]을 return 합니다.
🔥 TRY #1 무참히 실패
👉🏻 2, 3, 5, 7... 소수 뽑다가 이건 아니다 싶었음
👉🏻 심지어 첫 번째 테스트 케이스는 모두 2로 나누어지기 때문에 첫 번째 while문에 걸려야 하는 여기에서도 제대로 된 정답이 도출되지 않음
class Solution {
public int[] solution(int denum1, int num1, int denum2, int num2) {
int[] answer = new int[2];
if(num1 != num2) {
num1 = num1 * num2; // 분모 8
denum1 = denum1 * num2; // 분자1 4
denum2 = denum2 * num1; // 분자2 6
while(num1 % 2 == 0 && denum1 % 2 == 0 && denum2 % 2 == 0) {
num1 = num1 / 2; // 4
denum1 = denum1 / 2; // 2
denum2 = denum2 / 2; // 3
}
while(num1 % 3 == 0 && denum1 % 3 == 0 && denum2 % 3 == 0) {
num1 = num1 / 3;
denum1 = denum1 / 3;
denum2 = denum2 / 3;
}
while(num1 % 5 == 0 && denum1 % 5 == 0 && denum2 % 5 == 0) {
num1 = num1 / 5;
denum1 = denum1 / 5;
denum2 = denum2 / 5;
}
while(num1 % 7 == 0 && denum1 % 7 == 0 && denum2 % 7 == 0) {
num1 = num1 / 7;
denum1 = denum1 / 7;
denum2 = denum2 / 7;
}
}
answer[0] = denum1 + denum2;
answer[1] = num1;
return answer;
}
}
🔥 TRY #2 정의부터 제대로!
👉🏻 약수: 어떤 수를 정확하게 나누어 떨어지게 하는 수 (나머지가 0이 되도록 하는 수)
👉🏻 최대공약수는 0이 아닌 두 개 이상의 정수의 공통되는 약수 중에서 가장 큰 수
👉🏻 즉, a와 b의 최대공약수는 a의 약수이면서 b의 약수인 수 중에서 가장 큰 수
<최대공약수 조건>
👉🏻 최대공약수는 a, b와 같거나 작아야 함
👉🏻 a, b를 최대공약수로 나누었을 때 나머지는 0이어야 함
class Solution {
public int[] solution(int denum1, int num1, int denum2, int num2) {
int[] answer = new int[2];
int denum = 0; // 분자
int num = 0; // 분모
int max = 0; // 최대공약수
if(num1 != num2) {
num = num1 * num2; // 분모
denum = (denum1 * num2) + (denum2 * num1); // 분자
// 최대공약수 구하기
for(int i = 1; (i <= denum) && (i <= num); i++) { // 분모와 분자보다 작아야 함
if((denum % i == 0) && (num % i == 0)) {
max = i;
}
}
num = num / max;
denum = denum / max;
}
answer[0] = denum;
answer[1] = num;
return answer;
}
}
뭐야 왜 이래 ㄱ-
🔥 TRY #3 분모가 같을 때의 조건 추가
👉🏻 분모가 다를 때 계산하는 것에만 치중해서 분모가 같을 때의 조건을 넣지 않았음!
👉🏻 두 분모가 같다면 배열에는 분모 하나만 넣고(num1을 넣음), 각 분자를 더해서 넣으라는 조건 추가
class Solution {
public int[] solution(int denum1, int num1, int denum2, int num2) {
int[] answer = new int[2];
int denum = 0; // 분자
int num = 0; // 분모
int max = 0; // 최대공약수
if(num1 != num2) {
num = num1 * num2; // 분모
denum = (denum1 * num2) + (denum2 * num1); // 분자
// 최대공약수 구하기
for(int i = 1; (i <= denum) && (i <= num); i++) {
if((denum % i == 0) && (num % i == 0)) {
max = i;
}
}
num = num / max;
denum = denum / max;
answer[0] = denum;
answer[1] = num;
} else { // 분모가 같을 때
answer[0] = denum1 + denum2;
answer[1] = num1;
}
return answer;
}
}
🔥🎉 TRY #4 [실행 결과] 너무 어렵게 생각하지 말기
👉🏻 두 분모가 같을 경우에는 굳이 분모를 곱하고, 분자를 x자로 곱하고 할 필요가 없다고 생각해서 if/else 구문으로 묶었는데 아무리 생각해도 더 이상 로직이 생각나지 않았음
👉🏻 어차피 최대공약수로 나누면 다시 돌아오니까,, 하는 생각에 분모가 같을 때/다를 때에 대한 if/else 구문을 없애 줬더니 성공!
class Solution {
public int[] solution(int denum1, int num1, int denum2, int num2) {
int[] answer = new int[2];
int denum = 0; // 분자
int num = 0; // 분모
int max = 0; // 최대공약수
num = num1 * num2; // 분모
denum = (denum1 * num2) + (denum2 * num1); // 분자
// 최대공약수 구하기
for(int i = 1; (i <= denum) && (i <= num); i++) {
if((denum % i == 0) && (num % i == 0)) {
max = i;
}
}
num = num / max;
denum = denum / max;
answer[0] = denum;
answer[1] = num;
return answer;
}
}
💡추가로 최소공배수를 구하고 싶다면?
👉🏻 최소공배수 = (공통분모로계산된분자 * 공통분모) / 최대공약수
// 최소공배수 구하기
int min = (num*denum) / max;
출처: 프로그래머스 코딩 테스트 연습,https://school.programmers.co.kr/learn/challenges
코딩테스트 연습 | 프로그래머스 스쿨
개발자 취업의 필수 관문 코딩테스트를 철저하게 연습하고 대비할 수 있는 문제를 총망라! 프로그래머스에서 선발한 문제로 유형을 파악하고 실력을 업그레이드해 보세요!
school.programmers.co.kr