안녕하세요, 주인장입니다.
프로그래머스 레벨0을 졸업하고 레벨1을 풀고 있지만 벨로그 정리할 문제가 남아서 패드에 묵혀둔 노트를 풀어서 ㅋㅋㅋ
암튼 이번 문제는 최소공배수를 구하면 되는 쉬운 문제이긴 하지만, 생각을 여러 개 해보다가 몇 가지 해법을 소개해드리기 위하여 벨로그로 포스팅 하게 되었습니다.
📌 문제
머쓱이네 피자가게는 피자를 여섯 조각으로 잘라 줍니다. 피자를 나눠먹을 사람의 수 n이 매개변수로 주어질 때, n명이 주문한 피자를 남기지 않고 모두 같은 수의 피자 조각을 먹어야 한다면 최소 몇 판을 시켜야 하는지를 return 하도록 solution 함수를 완성해보세요.
네 그냥 한 마디로 입력 받는 N이랑 6의 최소공배수를 구하여 리턴하면 되는 간단한 문제입니다. 저는 코테 공부하면서 최근에 "유클리드 호제법" 알고리즘을 학습하여, 최대최소공배수를 구하는 알고리즘을 학습했고, 이로 먼저 풀이 하였습니다.
📌 해법(1) - 유클리드 호제법으로 최소공배수 구하기
public static int solution(int n) {
int answer = 0;
answer = n * 6 / gcd(n, 6);
return answer / 6;
}
public static int gcd(int a, int b) {
if(b == 0) return a;
else return gcd(b, a%b);
}
}최소 공배수를 구하기 위한 gcd함수를 추가적으로 작성해 최소 공배수를 구해주었습니다. 여기서 유클리드 호제법이 무엇인지 해당 알고리즘을 복습해 봅시다.
📌유클리드 호제법?
먼저, 유클리드 호제법이란 2개 이상의 숫자를 가지고 최대공약수를 구할 경우 두 수의 나머지가 0이 될때까지계속해서 반복하며 나머지를 구하는 방식
코드를 통해 살펴보자.
public class Main {
public static int GCD(int x, int y) {
if(y == 0) {
return x;
}
else {
return GCD(y, x % y);
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int x = Integer.parseInt(br.readLine());
int y = Integer.parseInt(br.readLine());
int result = GCD(x, y);
System.out.println(result);
}
}📌 해법(2) - 1부터 최대공약수까지
이 방법은 1부터 입력된 n과 6의 최대공약수까지 검사하면서 최소 공배수를 찾아내는 방법이다.
class Solution {
public int solution(int n) {
int answer = 0;
for(int i=1; i<=n*6;i++){
if (6 * i % n == 0) {
answer = i;
break;
}
}
return answer;
}
}유클리드 호제법 알고리즘을 최근에 배워서 그런가 함수 쓸 생각을 했는데 문제가 쉽긴 하지만 간단하게 최소공배수를 구할 수 있는 방법도 유용한 것 같다.
