과일 장수 / 모의고사 / 소수 만들기 / 기사단원의 무기 / 소수 찾기

1️⃣ 과일 장수

 

문제 설명

과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 1점부터 k점까지의 점수로 분류하며, k점이 최상품의 사과이고 1점이 최하품의 사과입니다. 사과 한 상자의 가격은 다음과 같이 결정됩니다.

• 한 상자에 사과를 m개씩 담아 포장합니다.
• 상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사과 한 상자의 가격은 p * m 입니다.

과일 장수가 가능한 많은 사과를 팔았을 때, 얻을 수 있는 최대 이익을 계산하고자 합니다.(사과는 상자 단위로만 판매하며, 남는 사과는 버립니다)

예를 들어, k = 3, m = 4, 사과 7개의 점수가 [1, 2, 3, 1, 2, 3, 1]이라면, 다음과 같이 [2, 3, 2, 3]으로 구성된 사과 상자 1개를 만들어 판매하여 최대 이익을 얻을 수 있습니다.

• (최저 사과 점수) x (한 상자에 담긴 사과 개수) x (상자의 개수) = 2 x 4 x 1 = 8

사과의 최대 점수 k, 한 상자에 들어가는 사과의 수 m, 사과들의 점수 score가 주어졌을 때, 과일 장수가 얻을 수 있는 최대 이익을 return하는 solution 함수를 완성해주세요.

 

제한사항

• 3 ≤ k ≤ 9
• 3 ≤ m ≤ 10
• 7 ≤ score의 길이 ≤ 1,000,000
  • 1 ≤ score[i] ≤ k
• 이익이 발생하지 않는 경우에는 0을 return 해주세요.

 

입출력 예

k	m	score	result
3	4	[1, 2, 3, 1, 2, 3, 1]	8
4	3	[4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2]	33

 

 

 

 

💻 나의 풀이

import java.util.*;
 
class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;   // 0으로 초기화
 
        Arrays.sort(score);   // 오름차순 정렬
 
        // 역순으로 순회
        // 구간의 끝(i)에서 시작하여 'm'만큼 건너뛰어 계산
        for(int i = score.length; i >= m; i -= m){  
            answer += score[i - m] * m;   // 현재 구간의 시작 인덱스(i-m)부터 m만큼의 원소를 곱하여 합산
        }
 
        return answer;
    }
}

 

최대 이익을 내려면 내림차순을 해야한다고 생각했습니다.

그런데 내림차순을  하려고 하니 메소드가 꽤나 복잡해지는거 같아서...어차피 반복문을 돌릴거니 일단 오름차순을 하고 반복문에서 거꾸로 실행하는 게 어떨까 하는 생각으로 풀었습니다.

 

 

---

 

2️⃣ 모의고사

 

문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

 

입출력 예

answers	return
[1,2,3,4,5]	[1]
[1,3,2,4,2]	[1,2,3]

 

 

 

💻 나의 풀이

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] solution(int[] answers) {
        // 순서o 
        // 길이가 5인 배열 안의 원소들이 순서대로 일치하는지?
        // 가장 높은 점수 받은 사람 리턴. 여럿일 경우 오름차순 정렬.
        
        int[] pattern1 = {1, 2, 3, 4, 5};    // 1번 수포자
        int[] pattern2 = {2, 1, 2, 3, 2, 4, 2, 5};    // 2번 수포자
        int[] pattern3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};    // 3번 수포자

        int[] scores = new int[3];    // 1,2,3번의 각 맞은 문제 갯수를 담을 배열

        // 정답answers의 길이만큼 순회하면서 수포자들 점수 계산.
        // 각 인덱스의 값이 일치하는지 비교. 일치한다면 해당 사람의 카운트 +1
        for (int i = 0; i < answers.length; i++) {
            if (answers[i] == pattern1[i%5]) scores[0]++;
            if (answers[i] == pattern2[i%8]) scores[1]++;
            if (answers[i] == pattern3[i%10]) scores[2]++;
        }

        // 가장 많이 맞은 점수 (최대값) 비교해서 담기
        int maxScore = Math.max(scores[0], Math.max(scores[1], scores[2]));

        // 정답이 여러 명일 수 있음 (동점자)
        List<Integer> winners = new ArrayList<>();

        // 각 scores를 순회하면서 최고점수랑 같은 사람을 winners 리스트에 담아주기
        // 인덱스는 0부터 이기 때문에 i+1을 해줌
        for (int i = 0; i < scores.length; i++) {
            if (scores[i] == maxScore) winners.add(i + 1);
        }

        // Integer 값을 int 배열로 변환해서 반환
        return winners.stream().mapToInt(Integer::intValue).toArray();
    }
}

 

수포자들 마다 각 규칙이 있는 것은 쉽게 알아챌 수 있습니다.

• 1번 수포자는 1~5번을 순서대로 5개씩 반복
• 2번 수포자는 모든 숫자의 앞에 2, 뒷 숫자는 1~5를 반복해서 8개씩 반복
• 3번 수포자는 31245 순서로 두번씩 반복해서 총 10개씩 반복

각각의 규칙을 담은 pattern이란 배열을 선언&초기화 해주는 것으로 표현해줍니다.

그리고 최종적으로 가장 많이 맞은 사람을 담으려면, 정답 개수를 카운트 해주는 변수도 필요하니 scores 배열을 길이 3으로 초기화 해줬습니다.

 

정답answers 배열을 순회하면서 각 인덱스의 값이 같은지 비교하고, 일치한다면 해당 사람의 카운트를 +1 증가시켜줍니다. 이 때 주의할 점은 각 패턴마다 반복되는 갯수만큼으로 나누어 주어야 합니다 ! ( 처음에 나누어주지 않고 그냥 비교해서 런타임 오류가 엄청 났습니다..ㅎㅎ )

 

그 후, 카운트한 걸로 최대값을 찾아내줄건데요.

총 세 사람의 값을 비교해야하니 Math.max() 메소드를 두번 중첩해줬습니다.

 

동점자가 여러 명일 수 있기 때문에 List를 사용해 winners 변수를 생성해주고, 최고 점수와 같은 사람을 winners 변수에 담아주는데, 여기에서 주의할 점은 인덱스는 0부터이기 때문에 i+1을 해줍니다. 그래야 0번, 1번, 2번이 아닌 1번, 2번, 3번이 되겠죠.

 

마지막으로 Integer 값을 int 배열로 변환해서 반환해주면 됩니다!

 

 

---

 

3️⃣ 소수 만들기

 

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

 

입출력 예

nums	result
[1,2,3,4]	1
[1,2,7,6,4]	4

입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.

 

입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

 

 

 

💻 나의 풀이

class Solution {
    public int solution(int[] nums) {
        // 3개의 수를 합해서
        // 소수인지 판별
        
        int answer = 0;
        
        // 3개의 수를 합하기
        for(int i=0; i<nums.length; i++) {
            for(int j=i+1; j<nums.length; j++) {
                for(int k=j+1; k<nums.length; k++) {
                   int sum = nums[i]+nums[j]+nums[k];
                    
                    // 소수 판별
                    boolean yn = false;
                    for(int n=2; n<sum; n++) {
                        if(sum % n == 0) yn = true;
                    }
                    if(!yn) answer++;                 
                }
            }
        }

        return answer;
    }
}

 

먼저 3중 for문으로 세 개의 수를 합했습니다.

그리고 소수판별을 해줍니다.

1. boolean yn = false; : 초기에 yn을 false로 설정합니다. 이 변수는 현재까지의 sum이 소수인지를 나타냅니다.
2. for(int n=2; n<sum; n++) : n을 2부터 시작하여 sum 이전까지의 모든 수에 대해 반복합니다. 여기서 n이 2부터 시작하는 이유는, 1은 이미 소수로 처리되었으므로 2부터 소수 여부를 확인하기 시작합니다.
3. if(sum % n == 0) yn = true; : 만약 sum이 n으로 나누어 떨어진다면 (sum이 n의 배수라면), yn을 true로 설정합니다. 이는 sum이 소수가 아니라는 것을 의미합니다.
4. if(!yn) answer++; : 반복이 끝난 후에도 yn이 여전히 false라면, 즉, sum이 어떤 수로도 나누어 떨어지지 않았다면 sum은 소수이므로 answer를 증가시킵니다.

 

 

🔍 다른 사람의 풀이

class Solution {
    public int solution(int[] nums) {
        int cnt = 0;
        for(int i=0; i<nums.length - 2; i++) {
            for(int j=i+1; j<nums.length - 1; j++) {
                for(int k=j+1; k<nums.length; k++) {
                    if(isPrime(nums[i] + nums[j] + nums[k])) {
                        cnt++;
                    }
                }
            }
        }

        return cnt;
    }

    public boolean isPrime(int num) {
        boolean isPrime = true;
        for(int i=2; i<=(int)Math.sqrt(num); i++) {
            if(num % i == 0) {
                isPrime = false;
                break;
            }
        }
        return isPrime;
    }
}

 

아예 isPrime 이라는 소수 판별 메서드를 따로 만들었네요!

이 메서드는 2부터 num의 제곱근까지의 모든 수로 나누어 보면서, 나누어 떨어지는 경우가 있는지 확인합니다. 나누어 떨어지는 경우는 소수가 아니므로 isPrime을 false로 설정하고 반복을 종료합니다.

 

여기서 중요하게 보아야 할 점은 num의 제곱근까지 확인한다는 건데요! 이유를 정리해보겠습니다.

 

1. 소수의 정의: 어떤 수가 소수인지 확인하려면, 그 수의 약수를 찾아보면 됩니다. 만약 그 수가 A와 B의 곱으로 나타낼 수 있다면, A와 B 중 하나는 반드시 그 수의 제곱근 이하의 값이 됩니다.
2. 반례 예시: 예를 들어, 16이라는 수가 주어졌을 때, 이 수의 제곱근은 4입니다. 만약 16이 어떤 수의 제곱이 아니라면, 그 수는 4보다 큰 어떤 소수로 나누어져야 합니다. 그런데, 이 소수는 16의 제곱근인 4보다 클 수 없습니다.
3. 효율성: 어떤 수의 제곱근 이상의 약수를 찾는 것은 비효율적입니다. 제곱근 이상의 약수는 항상 제곱근 이하의 약수보다 크기 때문에, 이미 제곱근 이하의 약수를 찾았다면 더 큰 약수는 찾을 필요가 없습니다.

 

 

---

 

 

4️⃣ 기사단원의 무기

 

문제 설명

숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다.

각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다.

예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로, 공격력이 4인 무기를 구매합니다. 만약, 이웃나라와의 협약으로 정해진 공격력의 제한수치가 3이고 제한수치를 초과한 기사가 사용할 무기의 공격력이 2라면, 15번으로 지정된 기사단원은 무기점에서 공격력이 2인 무기를 구매합니다. 무기를 만들 때, 무기의 공격력 1당 1kg의 철이 필요합니다. 그래서 무기점에서 무기를 모두 만들기 위해 필요한 철의 무게를 미리 계산하려 합니다.

기사단원의 수를 나타내는 정수 number와 이웃나라와 협약으로 정해진 공격력의 제한수치를 나타내는 정수 limit와 제한수치를 초과한 기사가 사용할 무기의 공격력을 나타내는 정수 power가 주어졌을 때, 무기점의 주인이 무기를 모두 만들기 위해 필요한 철의 무게를 return 하는 solution 함수를 완성하시오.

 

제한사항

• 1 ≤ number ≤ 100,000
• 2 ≤ limit ≤ 100
• 1 ≤ power ≤ limit

 

입출력 예

number	limit	power	result
5	3	2	10
10	3	2	21

입출력 예 #1

1부터 5까지의 약수의 개수는 순서대로 [1, 2, 2, 3, 2]개입니다. 모두 공격력 제한 수치인 3을 넘지 않기 때문에 필요한 철의 무게는 해당 수들의 합인 10이 됩니다. 따라서 10을 return 합니다.

 

입출력 예 #2

1부터 10까지의 약수의 개수는 순서대로 [1, 2, 2, 3, 2, 4, 2, 4, 3, 4]개입니다. 공격력의 제한수치가 3이기 때문에, 6, 8, 10번 기사는 공격력이 2인 무기를 구매합니다. 따라서 해당 수들의 합인 21을 return 합니다.

 

 

 

❌ 틀린 코드

import java.util.*;

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        
        for(int i=1;i<=number;i++){
            int cnt = 0;
            for(int j=1;j<=i;j++){
                if(i%j==0) cnt++;
            }
            
            if(cnt>limit) cnt = power;
            answer += cnt;
        }
        
        return answer;
    }
}

 

틀린 코드라기 보다는 시간초과가 된 코드입니다.

이중for문을 써서 i를 j로 나누어 떨어지면 약수이므로 약수의 개수를 증가시켰습니다.

그렇다면 왜 실패일까?

number의 최대가 10만이기 때문에, 이렇게 일반적인 약수를 구하는 방법 (이차원 for문과 나머지로 비교하는 방법)으로는 특정 테스트 케이스에서 timeout이 된다고 합니다.

약수의 개수를 구하는 다른 로직이 필요해서 다시 고민을 해봤습니다. 😂

 

 

💻 나의 풀이

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;

        //i의 약수의 개수와 limit을 비교
        for (int i = 1; i <= number; i++) {
            if (divisorCount(i) <= limit)    // 약수의 개수가 limit보다 크지않다면
                answer += divisorCount(i);   
            else
                answer += power;   // 크다면 문제에서 정해진 power가 됨
        }

        return answer;
    }
    
	// 약수 개수를 카운트하는 메서드
    public int divisorCount(int num) {
        int cnt = 0;
		
        // 제곱근인 경우 -> 제곱수의 전까지는 약수의 개수가 하나 더 있음이 보장
        // ex. 16의 제곱근인 4 전까지는 약수의 개수가 하나 더 있음 (1,2,4)
        // 따라서 for문은 i가 제곱근일때 까지 반복
        for (int i = 1; i * i <= num; i++) {
        	// i가 num이 제곱근일 경우 cnt++
            if (i * i == num)
                cnt++;
                
            // i×i=n이 아닌 경우에는 약수가 두 개씩 존재    
            // i가 제곱근이 아닌 약수일 경우 cnt += 2
            else if (num % i == 0) 
                cnt += 2;
        }
        
        return cnt;
    }
}

 

약수를 구하는 메서드의 for문의 범위를 조정해서 시간 복잡도를 줄여야 했습니다.

i가 number의 약수일 때, number/i도 약수이므로

for문의 범위를 제곱근까지로 설정해줍니다. ( i * i <= num; )

그리고 if문을 사용해

제곱근일 경우 => 개수를 1 증가 cnt++

제곱근이 아닐 경우 => 개수를 2 증가 cnt += 2 

 

제곱근일 경우에는 이해가 가는데

아닌 경우 왜 +2인지 잘 이해가 안갔던..문제였습니다.

 

 

 

🔍 다른 사람의 풀이

import java.util.*;

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        
        for(int i=1;i<=number;i++){
            int cnt = 0;
            for(int j=1;j*j<=i;j++){
                if(j*j==i) cnt++;
                else if(i%j==0) cnt+=2;
            }
            
            if(cnt>limit) cnt = power;
            answer += cnt;
        }
        
        return answer;
    }
}

 

1. 약수는 두 수의 곱이 자기 자신이 되는 것이기 때문에 제곱수를 제외하면 한 쌍으로 갖는다.
2. 약수 개수가 홀수개일 경우 약수의 개수는 가운데 수를 기준으로 같은 값을 같는다.
3. 약수 개수가 짝수개일 경우 약수의 개수는 서로 대응된다.

1로 인해 약수는 크게 제곱수와 제곱수가 아닌 경우로 나뉠 수 있으며, 2,3번으로 인해 중간 지점까지, 즉 위의 코드에서 j의 제곱이 i보다 작거나 같을때까지 탐색한 후 제곱수의 경우 1번만 카운트하고 나머지 수는 2번 카운트하면 됩니다.

이 방식을 적용하면 기존에 하나의 약수를 구하는데 O(n)만큼 소요되었다면 (O root(n))만큼 시간 복잡도를 감소시킬 수 있습니다.

 

 

---

 

 

5️⃣ 소수 찾기

 

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

제한사항

• n은 2이상 1000000이하의 자연수입니다.

 

입출력 예

n	result
10	4
5	3

 

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

 

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

💻 나의 풀이

class Solution {
    public int solution(int n) {
    	// 2는 소수이기 때문에 초기값 1로 선언
        int answer = 1;
        
        // 3부터 n까지 반복하여 현재의 수인 i가 소수라면(true) answer+1
        for (int i = 3; i <= n; i++) {
            if (isPrime(i)) answer += 1;
        }
        
        return answer;
    }
    
    // 소수 판별 메서드
    private boolean isPrime(int num) {
    	// 2부터 num의 제곱근까지 반복
        for (int i = 2; i <= (int) Math.sqrt(num); i++) {
        	// num이 i로 나눈 나머지가 0이면 소수가 아님
            if (num % i == 0) {
                return false;
            }
        }
        
        // 어떤 수로도 나누어지지 않으면 소수
        return true;
    }
}

 

먼저 1은 소수가 아니고, 2는 소수이기 때문에 answer를 1(개)로 초기화 시켜줬습니다.

3부터는 주어진 n까지 순회할건데, 만약 현재의 수 i가 isPrime() 이라는 소수 판별 메서드를 거친 결과가 true라면 소수라는 것을 의미하기 때문에 answer+1을 해줍니다.

그리고 answer를 반환하게끔 합니다.

 

그 다음은 isPrime() 메소드를 작성했는데요, 2부터 num의 제곱근까지 순회해줍니다.

제곱근까지만 확인하는 이유?

n이 어떤 수 a와 b의 곱으로 표현될 때, a와 b 중 적어도 하나는 반드시 n의 제곱근 이하의 값이기 때문입니다.

만약 n이 어떤 수 a와 b의 곱으로 이루어진 수라고 가정하면, a×b=n입니다. a와 b가 모두 n의 제곱근보다 크다면, a×b는 n보다 커지게 됩니다. 따라서 둘 중 적어도 하나는 n의 제곱근 이하의 값이어야만 a×b=n을 만족할 수 있습니다.

이렇게 하면 n이 소수인지를 판별하는 데에 불필요한 계산을 줄일 수 있습니다.

 

num을 i로 나눈 나머지가 0이라면 소수가 아니라는 뜻이기 때문에 false를 반환해줍니다.

어떤 수로도 나누어지지 않는다면 소수이므로 true를 반환해줍니다.

 

 

---

 

 

알바가기 전, 아침 일찍 일어나 2~3문제를 풀곤 했었는데요.

난이도가 높아짐에 따라 2문제도 못풀게 되는 것 같습니다.

그렇지만 조급하게 생각안하고 한 문제라도 제대로 고민해보고 풀어보고 이해하는 것에 집중하자고 스스로 다짐하고 있습니다..화이팅! 🔥