momo study(23.01.25)

오늘은 알고리즘 중 순열과 조합문제를 풀어보고 복습하는 시간을 가졌다.

 

5개 문제 중 레퍼런스 참고 없이 푸는데 성공한 건 한 문제 뿐이었다.

 

유클리드 호제법을 활용해 최대공약수를 구하면 쉽게 풀어나갈 수 있는 문제였는데, 레퍼런스 만큼이나 깔끔하고 보기 쉽게  코드를 짠 것 같아서 올려본다.

 

 

조건

한 회사의 팀장은 출근길에 아몬드 빼빼로 M개와 누드 빼빼로 N개를 구매하여 아침 일찍 출근길에 나섰습니다. 팀장은 출근한 직원 수에 따라 어떻게 빼빼로를 나누어 줄지 고민하고 있습니다. 여러분이 직원 수에 따라 빼빼로를 나누어 주는 방법을 구하는 솔루션을 제공해 주세요.

 

입력

인자 1: M

• int 타입의 양의 정수 (1 ≤ M ≤ 1,000,000,000)

인자 2: N

• int 타입의 양의 정수 (1 ≤ N ≤ 1,000,000,000)

출력

• ArrayList<Integer[]> 타입의 output을 리턴해야 합니다.
• output[i]은 다음과 같은 순서를 가진 길이 3의 배열입니다.
  • [빼빼로를 받게 되는 직원의 수, 나누어 주는 아몬드 빼빼로의 수, 나누어 주는 누드 빼빼로의 수]
• output은 output[i][0], 즉 '빼빼로를 받게 되는 직원의 수'를 기준으로 오름차순으로 정렬합니다.

 

입출력 예시

int M = 4;
int N = 8;
ArrayList<Integer[]> output = divideChocolateStick(M, N);
System.out.println(output);
// [[1, 4, 8], [2, 2, 4], [4, 1, 2]]

 

문제 풀이

public class Solution { 
    public ArrayList<Integer[]> divideChocolateStick(int M, int N) {
    // TODO:
    // M N의 최대공약수 구하고 새로운 인트에 할당하기
    int GCD = eucd(M, N);
    // 리턴할 값인 result생성하기
    ArrayList<Integer[]> result = new ArrayList<>();
    // 어떻게 짜야 result안에 [직원 수, 나누어줄M수, 나누어줄N수] 들을 add시킬까?
    // 최대공약수의 약수를 반복해서 돌면 아니지 어떤 수 i를 1부터 반복하면서
      for(int i = 1; i <= GCD; i++){
      // i가 최대공약수의 약수라면
        if(GCD % i == 0){
       // result에 add하기 result.add([직원 수i, M/i, N/i])
       result.add(new Integer[]{i, M/i, N/i});
        }
        else {};
      }
      return result;
  }
 
 
 
    // 최대공약수 구하기, 유클리드 호제법 ㄱ
    public int eucd(int m, int n) {
        // 큰숫자를 작은숫자로 나눈 나머지를 계산
        int r = m % n;
        // 나머지가 0이면 작은숫자가 최대공약수이므로 작은숫자 리턴
        if (r == 0) {
            return n;
        } else {
            // 나머지가 0 이상이면 재귀형태로 호출
            // 이때 파라미터는 작은숫자와 나머지를 넣어줌
            return eucd(n, r);
        }
    }
}

public int eucd 내부의 내용이 유클리드 호제법을 활용하여 입력받은 m과 n사이의 최대공약수를 구하는 로직이다.

유클리드 호제법의 내용은 잘 기억해 뒀다가 필요할 때 활용하면 좋을 것 같다.