DAY11 수학, 반복문

1️⃣ 주사위의 개수

 

문제 설명

머쓱이는 직육면체 모양의 상자를 하나 가지고 있는데 이 상자에 정육면체 모양의 주사위를 최대한 많이 채우고 싶습니다. 상자의 가로, 세로, 높이가 저장되어있는 배열 box와 주사위 모서리의 길이 정수 n이 매개변수로 주어졌을 때, 상자에 들어갈 수 있는 주사위의 최대 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• box의 길이는 3입니다.
• box[0] = 상자의 가로 길이
• box[1] = 상자의 세로 길이
• box[2] = 상자의 높이 길이
• 1 ≤ box의 원소 ≤ 100
• 1 ≤ n ≤ 50
• n ≤ box의 원소
• 주사위는 상자와 평행하게 넣습니다.

입출력 예

box	n	result
[1, 1, 1]	1	1
[10, 8, 6]	3	12

 

입출력 예 #1

• 상자의 크기가 가로 1, 세로 1, 높이 1이므로 모서리의 길이가 1인 주사위는 1개 들어갈 수 있습니다.

입출력 예 #2

• 상자의 크기가 가로 10, 세로 8, 높이 6이므로 모서리의 길이가 3인 주사위는 12개 들어갈 수 있습니다.

---

 

💻 나의 풀이

class Solution {
    public int solution(int[] box, int n) {
        int a = box[0]/n;
        int b = box[1]/n;
        int c = box[2]/n;     
        return a*b*c;
    }
}

 

가로 세로 높이에 들어갈 주사위의 개수를 a, b, c로 지정해주고 각 변을 n으로 나눠줍니다.

부피 = 가로*세로*높이를 해주면 상자에 들어갈 수 있는 주사위이 최대 개수가 나옵니다.

이렇게 세 개의 변수를 선언해서 구현하는 것보다 더 간단한 방법이 있을거 같은데...가독성은 가장 좋아보여 이 코드로 작성했습니다.

 

 

---

 

 

2️⃣ 합성수 찾기

 

문제 설명

약수의 개수가 세 개 이상인 수를 합성수라고 합니다. 자연수 n이 매개변수로 주어질 때 n이하의 합성수의 개수를 return하도록 solution 함수를 완성해주세요.

 

 

제한사항

• 1 ≤ n ≤ 100

입출력 예

n	result
10	5
15	8

 

입출력 예 #1

• 10 이하 합성수는 4, 6, 8, 9, 10 로 5개입니다. 따라서 5를 return합니다.

입출력 예 #1

• 15 이하 합성수는 4, 6, 8, 9, 10, 12, 14, 15 로 8개입니다. 따라서 8을 return합니다.

---

 

💻 나의 풀이

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for(int i=1; i<=n; i++){  // i가 1부터 자연수n까지 반복
            int a = 0;  // 약수의 개수 초기화
            for(int j=1; j<=n; j++){  // j가 1부터 자연수n까지 반복
                if(i%j == 0){  // i를 j로 나누어 떨어지면
                    a++;  // 약수의 개수 +1
                }
            }
            if(a>=3){
                answer++;  // 약수가 세 개 이상인 수 카운팅 +1
            }
        }
        return answer;
    }
}

 

i를 1부터 자연수 n까지 반복하게 하고, 이중for문으로 j도 1부터 자연수 n까지 반복되게 한 후, i를 j로 나눴을 때 나머지가 0인 경우에만 약수 a의 갯수를 증가시킵니다. 그리고 약수 a의 개수가 세 개 이상일 때 answer를 카운팅해 증가시켰습니다.

보통 약수, 소수 이런 것들은 알고리즘 공식이 따로 있는거 같은데... 아직 제 머리로는 떠오르지 않아서 이렇게 풀 수 밖에 없었습니다. 😂 이중for문에 if문까지 존재하니 가독성이 많이 떨어지는것 같네요...

 

 

🔎 다른 사람의 풀이

import java.util.stream.IntStream;

class Solution {
    public int solution(int n) {
        return (int) IntStream.rangeClosed(1, n).filter(i -> (int) IntStream.rangeClosed(1, i).filter(i2 -> i % i2 == 0).count() > 2).count();
    }
}

 

스트림은 볼 때 마다 신세계;

 

class Solution {
    public int solution(int n) {
        int[] arr = new int[n + 1];

        for (int i = 2; i <= n; i++) {
            arr[i] = 1;
        }
        for (int i = 2; i <= (int)Math.sqrt(n); i++) {
            if (arr[i] == 0) {
                continue;
            }
            int num = i * 2;
            while (num <= n) {
                 arr[num] = 0;
                 num += i;
            }
        }
        int answer = 0;
        for (int i = 2; i < arr.length; i++) {
            if (arr[i] == 0) {
                answer++;
            }
        }
        return answer;
    }
}

 

소수를 찾는 에라토스테네스의 체 방법에서 answer가 증가하는 조건만  'arr[i] == 1'에서 'arr[i] == 0'으로 변경한 방식이라고 합니다. 소수의 경우 arr[i] == 1이고,  합성수의 경우 arr[i] == 0 이 되는 원리를 이용합니다.

 

💡 에라토스테네스의 체 (Eratosthenes' Sieve)
소수를 찾는 간단하면서도 효과적인 알고리즘 중 하나입니다. 이 알고리즘은 특정 범위 내의 모든 소수를 찾아내는 데에 사용됩니다.

1. 초기화: 2부터 시작하는 모든 수를 후보로 선택합니다. 이 중에서 가장 작은 수를 소수로 선택하고, 그 배수들을 모두 제외합니다.
2. 다음 소수 찾기: 처음 선택한 소수를 기준으로 그 다음으로 큰 수를 찾습니다. 이 수를 다음 소수로 선택하고, 그 배수들을 다시 모두 제외합니다.
3. 반복: 위의 단계를 반복하면서 소수를 찾아나갑니다. 반복할 때마다 현재 소수의 배수를 제외하면서 소수를 찾아냅니다.
4. 완료: 반복을 계속하다가 지정된 범위 내의 모든 수를 확인하면 알고리즘을 종료합니다. 이때 남아 있는 모든 수는 소수입니다.

에라토스테네스의 체는 다수의 소수를 빠르게 찾을 수 있어서 주로 소수와 관련된 문제에서 활용됩니다. 이 알고리즘의 시간 복잡도는 대략 O(n log log n)으로 효율적입니다.

 

 

---

 

3️⃣ 최댓값 만들기 (1)

 

문제 설명

정수 배열 numbers가 매개변수로 주어집니다. numbers의 원소 중 두 개를 곱해 만들 수 있는 최댓값을 return하도록 solution 함수를 완성해주세요.

 

제한사항

• 0 ≤ numbers의 원소 ≤ 10,000
• 2 ≤ numbers의 길이 ≤ 100

입출력 예

numbers	result
[1, 2, 3, 4, 5]	20
[0, 31, 24, 10, 1, 9]	744

 

입출력 예 #1

• 두 수의 곱중 최댓값은 4 * 5 = 20 입니다.

입출력 예 #1

• 두 수의 곱중 최댓값은 31 * 24 = 744 입니다.

---

 

💻 나의 풀이

import java.util.Arrays;

class Solution {
    public int solution(int[] numbers) {
        Arrays.sort(numbers);  // 오름차순 배열
      return numbers[numbers.length-1] * numbers[numbers.length-2];  // 인덱스는 0부터 시작하기 때문에 -1 해줌
    }
}

 

배열에 있는 값 중에서 가장 큰 값 * 그 다음으로 큰 값을 하면 당연히 최댓값이 되게 됩니다.

이것을 다시 한번 더 생각해보자면, 배열을 오름차순으로 정렬했을 때 마지막 원소 두개를 곲하는 것과 같습니다. 물론 전부 양수이기 때문에 가능한 얘기입니다.

그러므로 배열을 Arrays.sort를 사용하여 오름차순으로 정렬해주고, 마지막 원소 두 개를 곱해주면 해결됩니다. 이 때, 인덱스는 0부터 시작하기 때문에 -1 을 해줍니다.

 

---

 

 

4️⃣ 팩토리얼

 

문제 설명

i팩토리얼 (i!)은 1부터 i까지 정수의 곱을 의미합니다. 예를들어 5! = 5 * 4 * 3 * 2 * 1 = 120 입니다. 정수 n이 주어질 때 다음 조건을 만족하는 가장 큰 정수 i를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• 0 < n ≤ 3,628,800

입출력 예

n	result
3628800	10
7	3

 

입출력 예 #1

• 10! = 3,628,800입니다. n이 3628800이므로 최대 팩토리얼인 10을 return 합니다.

입출력 예 #2

• 3! = 6, 4! = 24입니다. n이 7이므로, 7 이하의 최대 팩토리얼인 3을 return 합니다.

---

💻 나의 풀이

class Solution {
    static int factorial(int a) {
        if (a <= 1) {
            return a;
        } else {
            return factorial(a - 1) * a;
        }
    }
    public int solution(int n) {
        int answer = 0;
        
        for (int i = 1; i <= 10; i++) {
            if (factorial(i) <= n) {
                answer = i;
            }
        }
        return answer;
    }
}

 

팩토리얼만 보면 왜 이렇게 고등학생 때가 생각나는지...🙄

아무튼 재귀함수를 이용하여 해결했습니다.

팩토리얼을 재귀적으로 계산하는 메서드인 factorial을 작성해줍니다. factorial(a-1)*a를 a가 1이 될 때까지 실행하게 됩니다.

그리고 제한사항을 참고하여 1부터 10까지 반복하게 했습니다. 주어진 수 n을 기준으로 1부터 10까지의 정수 i에 대해 i! 가 n 이하일 때의 최대 i 값을 찾습니다.

 

 

🔎 다른 사람의 풀이

class Solution {
    public int solution(int n) {
        int fac = 1;
        int i = 0;

        while(true){
            if(fac <= n){
                fac *= i + 1;
                i++;
            }else break;
        }

        return i-1;
    }
}