[99club/TIL] 2주차 - 수요일 TIL(Today I Learned)

안녕하세요. delay100 입니다!

벌써 내일이 세션 날이군요..ㄷㄷ 요새 시간이 너무 빠른 것 같아요

---

미들러 문제

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

프로그래머스

 

1. 실패 코드 - 시간 초과

2중 for 문을 이용하였고, 약수를 구하기 위해 아래와 같이 코드를 진행시켰습니다.

i는 현재 구할 수의 값, j는 1부터 i까지 돌며 i%j가 나누어 떨어지는지 확인합니다.

// 약수를 구하기 위해 현재 숫자인 i값에 대해 j값을 1씩 증가하여 약수인지 판별
i= 1 /j= 1
cnt=1


i= 2 /j= 1
cnt=1
i= 2 /j= 2
cnt=2


i= 3 /j= 1
cnt=1
i= 3 /j= 2
i= 3 /j= 3
cnt=2


i= 4 /j= 1
cnt=1
i= 4 /j= 2
cnt=2
i= 4 /j= 3
i= 4 /j= 4

그러나 이 방법은 시간복잡도가 최대 10^5 * 10^5까지 가능하므로 시간초과가 날 수 밖에 없습니다.

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        
        // 1부터 5까지 약수 개수 list
        // [1, 2, 2, 3, 2]
        // 1
        // 1, 2
        // 1, 3
        // 1, 2, 4
        // 1, 5
        
        // 1. 1~n 약수 개수 만들기
        for(int i=1; i<(number+1); i++) {
            int cnt = 0;
            // 약수를 아는 방법?
            for(int j=1; j<=i; j++) {
                if(i%j==0) {
                    cnt++;
                }
            }
            
            // 2. 각 값이 limit을 넘는지 확인
            // -> 넘으면 power값으로 cnt(약수 개수)값 변환
            answer += (cnt > limit ? power : cnt);
        }
        
        
        return answer;
    }
}

코드 제출 시 테스트케이스 11~16, 18, 24, 25가 시간 초과로 통과되지 않고 있습니다.

 

2. 성공 코드

실패코드 때와 큰 틀은 동일합니다.

1. 약수의 개수 만들기 -> 변경

2. 각 약수가 limit값이 넘는지 확인하고 answer에 추가하기 -> 1번 코드 그대로 유지

 

약수의 개수를 구할 때 최대 연산횟수가 10^5*10^5이기 때문에 10억이 넘어가는 숫자가 나옵니다.

이걸 줄여줄 건데, j의 값을 Math.sqrt를 이용해서 제곱근까지만 계산할겁니다.

1~1000까지 약수가 정리된 링크를 클릭해서 째려보면, 현재 숫자의 제곱근까지만 봐도 그 개수 값을 알 수 있습니다.

1~1000까지 약수

예를 들어, 50의 제곱근은 7.0710678118654755 입니다.

50의 약수는 1, 2, 5, 10, 25, 50인데, 1, 2, 5만 확인해도 10, 25, 50은 저절로 알게 됩니다.

따라서 1, 2, 5에 도달한 경우 cnt +2를 해줍니다.

 

만약 4와 같이 제곱근 값이 약수인 수가 있을 수도 있는데, 이 때는 cnt를 +1을 해줍니다.

(4의 약수는 1, 2, 4)

// 핵심 코드
// 약수의 개수 구하기
for(int j=1; j<= Math.sqrt(i); j++) {               
    if(j==Math.sqrt(i)) cnt++;
    else if(i%j==0) {
        cnt+=2;
    }
}

따라서 핵심 코드는 위와 같고, 전체 코드는 아래와 같습니다.

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        
        // 1부터 5까지 약수 개수 list
        // [1, 2, 2, 3, 2]
        // 1
        // 1, 2
        // 1, 3
        // 1, 2, 4
        // 1, 5
        
        // 1. 1~n 약수 개수 만들기
        for(int i=1; i<(number+1); i++) {
            int cnt = 0;
            // 약수를 아는 방법?
            for(int j=1; j<= Math.sqrt(i); j++) {
                if(j==Math.sqrt(i)) cnt++;
                else if(i%j==0) {
                    cnt+=2;
                }
            }
            
            // 2. 각 약수 개수 값이 limit을 넘는지 확인
            // -> 넘으면 power값으로 약수 개수(cnt)값 변환
            answer += (cnt > limit ? power : cnt);
            
        }
        
        return answer;
    }
}

 

---

+ 비기너 문제

행렬의 덧셈 (https://school.programmers.co.kr/learn/courses/30/lessons/12950)

프로그래머스

 

+ 챌린저 문제

무인도 여행 (https://school.programmers.co.kr/learn/courses/30/lessons/154540)

프로그래머스

---

감사합니다.