알고리즘_JAVA_07

🐤 Before

Algorithm : 연산법

수학과 컴퓨터과학에서 사용되는, 문제 해결 방법을 정의한 '일련의 단계적 절차'이자 어떠한 문제를 해결하기 위한 '동작들의 모임'이다. 계산을 실행하기 위한 단계적 규칙과 절차를 의미하기도 한다.

[ 즉, 어떤 문제를 해결하기 위한 명확한 정차와 규칙의 집합이다. ]

"알고리즘은 코딩의 효율성과 확장성을 결정짓는 핵심 요소"

---

🐤 Info

주제 : 피자 나눠먹기 (2)
레벨 : ★☆☆☆☆

문제
피자가게는 피자를 여섯 조각으로 잘라 줍니다. 피자를 나눠먹을 사람의 수 n이 매개변수로 주어질 때, n명이 주문한 피자를 남기지 않고 모두 같은 수의 피자 조각을 먹어야 한다면 최소 몇 판을 시켜야 하는지를 return 하도록 solution 함수를 완성해보세요.

//Base Code
class Solution {
    public int solution(int n) {
        int answer = n;
        return answer;
    }
}

---

🐤 Think

피자가 한판에 6조각이다. 6명이 먹으면 남기지 않고 모두 먹는다.
하지만 7~11명이면 피자를 2판 시켜야하는데 피자가 남게된다.
즉 6, 12, 18의 값으로 피자를 주문하는 함수를 만들어야 한다.

결과적으로 사고에 실패했다.

이 문제는 최소 공배수를 활용하면 된다고 한다.

피자는 6조각으로 나눠지므로, N명이 동일한 조각을 먹으려면 6과 N의 초소공배수를 구한 후, 그것을 6으로 나누면 필요한 피자 판수가 나온다.

-> 최초 문제 이해는 했지만 결과적으로 풀이법을 알아내 알고리즘을 만들어내지 못했다.
모르는것을 발견했다는건 성장할 여지가 있다는 것이므로 긍정적이다.

---

🐤 Final Code

class Solution {
    public int solution(int n) {
        return lcm(n, 6) / 6;
    }

    // 최대공약수(GCD) 계산 (유클리드 호제법)
    private int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    // 최소공배수(LCM) 계산
    private int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }
}

---

🐤 Other Way

class Solution {
    public int solution(int n) {
        int answer = 1; // 최소 1판부터 시작

        while (true) {
            if (6 * answer % n == 0) break; 
            // 6 * answer이 n으로 나누어 떨어지면 종료
            answer++; 
            // 나누어 떨어질 때까지 피자 판 수 증가
        }

        return answer;
    }
}

반복문을 이용해서 최소한의 피자 판 수를 찾는 방법이다.
answer 을 1로 설정하고 while 문을 돌면서 조건에 만족하는 값을 찾는다.

6 * answer % n == 0 일 때 break이다.
즉, 6조각씩 있는 피자가 n(사람수)와 일치하여 0이 될 때 종료.

4명이 사람을 가정하면
6 1 = 6, 6 % 4= 2 이므로 2조각이 남아서 다시 돌린다
6 2 = 12, 12 % 4 = 0 딱 떨어저 남는 값이 0 이므로
2판으로 종료.

이렇게 사고를 다양한 방향으로 했다면, 기본적인 문법으로도 충분히 풀 수 있는 문제다.

---