분수의 덧셈
https://school.programmers.co.kr/learn/courses/30/lessons/120808
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
1) 문제
두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.
0 <numer1, denom1, numer2, denom2 < 1,000
2) 예시
numer1 | denom1 | numer2 | denom2 | 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 합니다.
3) 풀이
0. 영단어
최대공약수 = GCD ( Greatest Common Devider )
분자 = Numerator
분모 = Denominator
1. 클래스 선언을 해줍니다
● class Solution {
클래스명은 대문자로 시작해야하고, 정답이라는 의미로 Solution이라는 단어를 사용하였습니다.
2. 메소드 선언을 해줍니다.
● public int[] solution(int numer1, int denom1, int numer2, int denom2) {
정수 numer1 및 2, denom1 및 2를 매개변수로 사용하는 solution 메소드를 선언해줍니다.
메소드의 결과값인 solution은 정수배열이 나오므로, 데이터 타입을 int로 해줍니다.
3. 분모 및 분자에 대한 제한사항을 확인하고, 만족하지 않는다면 예외처리합니다.
● if (numer1 <= 0 || denom1 <= 0 || numer2 <= 0 || denom2 <= 0 ||
numer1 >= 1000 || denom1 >= 1000 || numer2 >= 1000 || denom2 >= 1000) {
throw new IllegalArgumentException("입력값이 제한사항을 벗어납니다.");
}
4. 먼저 두개의 분수 합을 구합니다.
두 분모의 곱으로 통분하여 합하는 식으로 계산해줍니다.
이렇게 나오는 값을 이제 최대공약수로 나누어주어야 기약분수가 됩니다.
● int resultNumer = numer1 * denom2 + numer2 * denom1;
int resultDenom = denom1 * denom2;
5. 먼저 두개의 분수 합을 구합니다.
두 분모의 곱으로 통분하여 합하는 식으로 계산해줍니다.
이렇게 나오는 값을 이제 최대공약수로 나누어주어야 기약분수가 됩니다.
● int resultNumer = numer1 * denom2 + numer2 * denom1;
int resultDenom = denom1 * denom2;
6. 클래스 내에 새로운 gcd(최대공약수) 메소드를 만듭니다.
이 때, 유클리드 호제법을 이용해서 최대공약수를 구합니다.
※ 유클리드호제법
고대 그리스 수학자 유클리드로부터 기원한 최대공약수를 두 개의 정수로 구할 때 사용하는 알고리즘의 하나입니다.
알고리즘의 방식은 이러합니다.
1) 두 정수 a와 b의 최대 공약수는 b와 a를 b로 나눈 나머지의 최대 공약수와 같다.
즉, GCD(a, b) = GCD(b, a % b).
2) 나머지가 0이 되면 그때의 b가 최대 공약수이다.
● private int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
예시)
a가 75, b가 48이라면
★ 첫번째 반복
int temp = 48
b = 75 % 48 = 27
a = 48
∴ a = 48, b = 27
★ 두번째 반복
int temp = 27
b = 48 % 27 = 21
a = 27
∴ a = 27 , b = 21
★ 세번째 반복
int temp = 21
b = 27% 21= 6
a = 21
∴ a = 21, b = 6
★ 네번째 반복
int temp = 6
b = 21 % 6 = 3
a = 6
∴ a = 6, b = 3
★ 다섯번째 반복
int temp = 3
b = 6 % 3 = 0
a = 3
∴ a = 3, b = 0
여기서 반복 종료. 최대공약수는 3이 나옵니다.
7. 최대공약수를 구하는 메소드에 위에 두 분수를 구해서 나온 분자, 분모값을 넣어서 나온 정수 gcd 값을 선언해줍니다.
최대공약수로 다시 분자와 분모를 나눠서, 기약분수가 될 분자 및 분모값이 되게합니다.
● int gcd = gcd(resultNumer, resultDenom);
resultNumer = resultNumer/gcd;
resultDenom = resultDenom/gcd;
8. 기약분수의 분자, 분모를 배열로 가지는 result 배열을 선언해줍니다.
그리고 그 배열을 반환해줍니다.
● int[] result = {resultNumer, resultDenom};
return result;
}
4) 코드
class Solution {
public int[] solution(int numer1, int denom1, int numer2, int denom2) {
// 제한사항 확인
if (numer1 <= 0 || denom1 <= 0 || numer2 <= 0 || denom2 <= 0 ||
numer1 >= 1000 || denom1 >= 1000 || numer2 >= 1000 || denom2 >= 1000) {
throw new IllegalArgumentException("입력값이 제한사항을 벗어납니다.");
}
// 분자와 분모를 더한 값 계산
int resultNumer = numer1 * denom2 + numer2 * denom1;
int resultDenom = denom1 * denom2;
// 최대 공약수를 계산하여 기약 분수로 만듦
int gcd = gcd(resultNumer, resultDenom);
resultNumer = resultNumer/gcd;
resultDenom = resultDenom/gcd;
// 결과를 배열로 반환
int[] result = {resultNumer, resultDenom};
return result;
}
// 최대 공약수를 계산하는 메서드
private int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
}
'Programmers Coding Test > Java' 카테고리의 다른 글
[프로그래머스 120813] Java - 코딩테스트 입문 / 짝수는 싫어요 (1) | 2024.01.30 |
---|---|
[프로그래머스 120812] Java - 코딩테스트 입문 / 최빈값 구하기 (0) | 2024.01.30 |
[프로그래머스 120811] Java - 코딩테스트 입문 / 중앙값 구하기 (0) | 2024.01.29 |
[프로그래머스 120821] Java - 코딩테스트 입문 / 배열 뒤집기 (1) | 2024.01.28 |
[프로그래머스 120826] Java - 코딩테스트 입문 / 특정 문자 제거하기 (1) | 2024.01.28 |