[부트캠프] TIL - 약수의 갯수, MySQL

문제 : 코딩테스트 연습 - 기사단원의 무기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

첫번째 풀이

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        
        //기사의 번호
        for(int i=1; i<=number; i++){
            int divisor = divisorCount(i);
            if(divisor <= limit)
                answer += divisor;
            else
                answer += power;    //리미트를 넘으면 power를 설정.
        }
        
        return answer;
    }
    //약수의 갯수 알고리즘, Math.sqrt()를 사용한 방법.
    public int divisorCount(int n){
        if(n==1)
            return 1;
        else if(n==2)
            return 2;
        else{
            int count =1;	//i==n인 경우를 미리 카운트해둔것
            for(int i=1; i<n/2; i++){
                if(n%i==0)
                	count++;
            }
            return count;
        }
    }
}

 

효율

 

 

for(int i=1; i<=n; i++)로 전부 순회하며 카운팅하는 방법이 있지만, 사실 케이스 하나하나 생각해보면

i <n/2까지만 순회하고 i==n 인 경우는 따로 count 해주는 방법 역시 동일하다는 것을 알 수  있습니다.

(어차피 절반을 넘어간 숫자들은 n값을 어떻게 해도 나눌 수 없기때문)

하지만, 이방법 역시 효율성은 개선되었으나 좋다고 할 수 없습니다

빅 오의 개념으로 O(n/2)는 결국 O(n)이니까요.

 

 

나의 풀이

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        
        //기사의 번호
        for(int i=1; i<=number; i++){
            int divisor = divisorCount(i);
            if(divisor <= limit)
                answer += divisor;
            else
                answer += power;    //리미트를 넘으면 power를 설정.
        }
        
        return answer;
    }
    //약수의 갯수 알고리즘, Math.sqrt()를 사용한 방법.
    public int divisorCount(int n){
        if(n==1)
            return 1;
        else if(n==2)
            return 2;
        else{
            int count =0;
            for(int i=1; i<(int)Math.sqrt(n)+1; i++){
                if(i*i==n)
                    count++;
                else if(n%i==0)
                    count+=2;
            }
            return count;
        }
    }
}

 

효율

 

Math.sqrt(n)까지를 범위로 산정합니다, 그리고 카운트 시에는 +=2 로 두개씩 카운트를 해주는겁니다.

이유는 예시로 따져보면 바로 이해가 가능합니다.

ex) n= 10 -> for(int i=1; i<=3; i++)

i==1 -> n/1 = 10, n%i==0 약수는 1 과 10 

i==2 -> n/2 = 5, n%i==0    약수는 2 와 5

i==3 -> n/3 = 3, n%i !==0

따라서 약수는 1, 2, 5, 10  

하지만 주의해야하는 부분이 있습니다, 바로 i*i==n인경우이면서 n%i==0인경우, 바로 n==100일 때 i==10인경우입니다.

이때는 따로 조건문을 사용하여 count를 1만 올려주도록합니다.

 

---

코딩테스트 연습 - 년, 월, 성별 별 상품 구매 회원 수 구하기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

MySQL 문제를 풀며 

COUNT(DISTINCT U.USER_ID) 를 작성하지 못하고 COUNT(*)를 사용하여 계속 오답을 출력했었다.

그리고 답을 참고하는 도중 년도와 월을 출력하기위해 DATE_FORMAT(O.SALES_DATE,'%Y'),

DATE_FORMAT(O.SALES_DATE,'%c') 말고 YEAR(O.SALES_DATE) , MONTH(O.SALES_DATE) 만으로

간단하게 출력가능하다는 것도 알게되어 둘을 정리합니다.

 

문제의 요구사항은 이러합니다.

 

보자마자 년, 월, 성별을 GROUP BY로 지정하고 회원의 수를 COUNT()하면 되겠다 라는 생각이 드는 조건입니다.

성별정보가 없는 경우 역시 IS NOT NULL을 사용할 수 있겠습니다.

 

하지만, 어째서 COUNT() 안에 DISTINCT U.USER_ID 가 들어가서 중복된 USER_ID를 허용하지 않게 되었는가?

 

바로 ONLINE_SALE 테이블에는 판매 정보를 담고 있고 JOIN을 하면서 중복되는 데이터가 발생하게되는것. 

 

SELECT YEAR(O.SALES_DATE) AS YEAR, MONTH(O.SALES_DATE) AS MONTH, U.GENDER, COUNT(DISTINCT U.USER_ID) AS USERS
FROM USER_INFO U INNER JOIN ONLINE_SALE O ON U.USER_ID = O.USER_ID
WHERE U.GENDER IS NOT NULL
GROUP BY YEAR(O.SALES_DATE), MONTH(O.SALES_DATE), U.GENDER
ORDER BY YEAR(O.SALES_DATE), MONTH(O.SALES_DATE), U.GENDER;