💪🏻 programmers Lv1(24.10.22 - 5문제)

programmers Lv1(24.10.22 - 5문제)

60) 과일 장수

• 사과 박스의 최대 이익을 구해야 되기 때문에 내림차순 정렬을 한다.

• 내림차순 정렬을 할 때 한 박스에 m개씩 담아야되기 때문에 i-=m으로 설정한다.

• i-m+1>=0을 하는 이유는 상자에 m개씩 담길 때만 조건을 만족해야 되기 때문이다.

  • m = 4일 때 i = 0, 1, 2 일 때는 3개이므로 만족하지 않고 i = 3이 되는 순간 4개가 박스에 들어가므로 가능하다.

import java.util.*;
class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        
        Arrays.sort(score);
        
        for(int i=score.length-1;i>=0;i-=m)
        {
            if(i-m+1>=0)  // 3-4+1
            {
                answer+=score[i-m+1]*m; //그 범위에서 가장 작은 값
            }
        }
        
        return answer;
    }
}

---

61) 소수 찾기

• 에라토네스의 체 알고리즘 활용

  • 소수를 판별하는 알고리즘

    • boolean 타입으로 isPrime 배열 선언

    • 먼저 소수는 1이 포함되지 않으므로 2부터 시작해서 n까지 소수라고 가정한다.

    • 배수들을 지울 때는 제곱근까지만 검사하면 된다.

    • 예시로 n=10이라고 가정하겠다. 그렇다면 i=2일 때, 두 번째 반복문에서 i=2; ii=4<=10이므로 통과가 되고 isPrime[i] = true이면서 j=ii ~n까지 j+i번을 반복한다. 그렇다면 4, 6, 8, 10이 2의 배수이기 때문에 답에서 제외가 된다.

    • 그 다음 i=3일 때를 보면 i*i= 9<=10 통과가 되고, isPrime[i] = true, 3의 배수를 지우면 3, 6, 9가 제외가 된다.

    • i=4 일 때는 이미 제외되었고, i=5 일 때 두 번째 반복문에서 통과되지 않고, i=6일 때 이미 제외가 되었고, i=7일 때도 두 번째 반복문에서 통과되지 않았고, i= 8, 9, 10은 다 제외되었다.

    • 따라서 답은 [2, 3, 5, 7]이 된다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean[] isPrime = new boolean[n+1];
        
        for(int i=2;i<=n;i++)
        {
            isPrime[i] = true; // 처음 모든 수는 소수라고 가정
        }
        
        for(int i=2;i*i<=n;i++)
        {
            if(isPrime[i])
            {
                for(int j= i*i;j<=n;j+=i)
                {
                    isPrime[j] = false;
                }
            }
        }
        
        for(int i=2;i<=n;i++)
        {
            if(isPrime[i])
            {
                answer++;
            }
        }
        return answer;
    }
}

---

62) 소수 만들기

• 먼저 3중for문을 이용해서 3개의 수를 더했을 때 합을 구한 뒤, 메서드를 만들어서 소수인지 계산해서 횟수를 구했다.

• isPrime()메서드는 소수는 2부터 시작이므로 1일 때 제외를 시키고 약수는 제곱근까지 구하면 되므로 i*i로 구한다.

• 그 다음 예를 들어 num이 13이면 13 % i == 0이 성립되지 않으므로 소수이고 num이 6이면 6%i==0이 성립되므로 소수가 아니다.

import java.util.*;
class Solution {
    public boolean isPrime(int num)
    {
        if(num<2) return false;
        for(int i=2;i*i<=num;i++)
        {
            if(num%i==0)
            {
                return false;
            }
        }
        return true;
    }
    public int solution(int[] nums) {
        int answer = 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++)
                {
                    int sum = nums[i] + nums[j] + nums[k];
                    
                    if(isPrime(sum))
                    {
                        answer++;
                    }
                }
            }
        }
        
        return answer;
    }                            
}

---

63) 덧칠하기

• 그리디 알고리즘 활용

• 매 단계 가장 최선의 선택을 하여 최종적인 결과를 도출하는 방법

• start는 현재 블록의 시작 위치를 나타냄. answer은 필요한 블록의 개수를 세는 변수로 첫 번 째 구역을 덮기 때문에 1로 초기화된 것.

• if(start+m > item) 조건은 현재 블록이 해당 구역을 덮을 수 있는지 판단.

• 덮는다면 continue를 통해 다음 구역으로 넘어가고, 아니라면 answer의 개수 증가

class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 0;
        
        int start = section[0];
        answer++;
        
        for(int item : section) // 2 3 6
        {
            if(start+m > item) // 2+4 = 6 > 2, 6>6
            {
                continue;
            }
            start = item;
            answer++;
        }
        return answer;
    }
}

---

64) 응말이(2)

• 발음할 수 있는 배열을 words로 만든다.

• 향상된 for문을 이용하여 babbling 배열을 b에 넣고 modified 변수에 복사한다.

• 연속된 발음이면 continue를 통해 다음으로 넘어간다.

• 그리고 replace() 메서드를 이용해 발음을 공백으로 대체한다.

• 남은 문자열이 공백인지 확인하고 단어를 완전히 발음할 수 있으므로 횟수를 카운트 한다.

• trim() : 문자열의 시작과 끝에 있는 공백을 제거한다. ex) "hello "를 trim()하면 "hello"가 된다.

• isEmpty() : 문자열이 비어 있는지 확인한다. 비어있는 문자열의 경우 true, 그렇지 않으면 false 반환

class Solution {
    public int solution(String[] babbling) {
        int answer = 0;
        
        for(String b:babbling)
        {
            String modified = b;
            
            String[] words = {"aya", "ye", "woo","ma"};
            
            if (b.contains("ayaaya") || b.contains("yeye") || b.contains("woowoo") || b.contains("mama")) {
                continue;
            }
            
            for(String word : words)
            {
                modified = modified.replace(word," ");
            }
            if(modified.trim().isEmpty())
            {
                answer++;
            }
        }
        return answer;
    }
}