10일차 - 알고리즘 코드카타

- 진행

일자	완료 번호
24.07.16	1~20
24.07.17	21~35
24.07.18	36~42
24.07.19	43~47
24.07.22	48~50
24.07.23	51~55
24.07.24	56~57
24.07.25	58
24.07.26	59~60

 

- 회고

59. 덧칠하기 : https://school.programmers.co.kr/learn/courses/30/lessons/161989

프로그래머스

- 풀이과정

class Solution {
    public int solution(int n, int m, int[] section) {
        int u = 1;
        int answer = 1;
        
        if(m == 1){
            return section.length;
        }else{
            for(int i = 1; i < section.length; i++){
                int p = section[i] - section[i - 1];
                if(p <= (m - u)){
                    u += p;
                }else{
                    u = 1;
                    answer++;
                }
            }
        }
        return answer;
    }
}

1. 페인트를 사용한 범위 변수 u를 선언하고 1로 초기화
2. 정답 변수 answer을 선언하고 1로 초기화
3. 만약 롤러의 길이가 1이라면 칠해야하는 벽 section의 길이를 정답으로 return
4. 아니라면 칠해야하는 벽 section을 순회하며 칠해야 하는 벽과 벽사이의 거리 변수 p를 선언
5. 벽과 벽사이의거리 p가 (롤러의길이 - 사용한 범위) 보다 작거나 같으면 롤러를 한번 더 사용하고
   사용한 범위 증가
6. 벽과 벽사이의거리 p가 (롤러의길이 - 사용한 범위) 보다 크다면 롤러를 리셋하고 정답 +1

60. 기사단원의 무기 : https://school.programmers.co.kr/learn/courses/30/lessons/136798

프로그래머스

- 풀이과정

Time: 107.72 ms, Memory: 73.6 MB

class Solution {
    public int solution(int number, int limit, int power) {
        int[] factors = new int[number];
        factors[0] = 1;
        int answer = 0;

        for(int i = 2; i <= number; i++){
            int m = 0;
            int sqrt = (int) Math.sqrt(i);
            for(int j = 2; j <= sqrt; j++){
                if(i % j == 0){
                    m++;
                }
            }
            if(sqrt * sqrt == i){
                m = m * 2 + 1;
            }else{
                m = m * 2 + 2;
            }

            if(m <= limit){
                factors[i - 1] = m;
            }else{
                factors[i - 1] = power;
            }
        }
        for(int a : factors){
            answer += a;
        }
        return answer;
    }
}

1. 약수를 구할 때 완전제곱수인경우 제곱근까지의 약수 * 2 + 1 아닐경우 * 2를 하면 갯수가 나온다.
2. 위 식의 경우 1 즉 factors[0]의 경우 무조건 1이기 때문에 대입해준다.
3. 1과 자기 자신의 경우 무조건 포함이기 때문에 루프를 2부터 돌리고 마지막에 2를 더해준다.
4. limit에 따라 factors에 대입해준다.
   ※ 몇몇 케이스에서 시간이 오래걸리는 경우가 발생
       효율적인방법을 찾아보니 에라토스테네스의 체라는 알고리즘이 있다는걸 확인했다.

- 개선 코드(속도 개선 107.72 → 9.87)

Time: 9.87 ms, Memory: 78.9 MB

class Solution {
    public int solution(int number, int limit, int power) {
        int[] factors = new int[number + 1];
        int answer = 0;

        // 에라토스테네스의 체 변형을 사용하여 약수의 개수 계산
        for (int i = 1; i <= number; i++) {
            for (int j = i; j <= number; j += i) {
                factors[j]++;
            }
        }

        // 제한 및 파워 적용
        for (int i = 1; i <= number; i++) {
            if (factors[i] > limit) {
                factors[i] = power;
            }
            answer += factors[i];
        }

        return answer;
    }
}