8/9

Today's Codekata

// 기사단원의 무기
class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        
        while (number > 0) {
            int damage = 0;
            for (int i = 1; i <= number; i++) {
                if (number % i == 0) {
                    damage++;
                }
            }
            if (damage > limit) {
                damage = power;
            }
            answer += damage;
            number--;
        }
        
        return answer;
    }
}

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

        for (int i = 1; i <= number; i++) {
            for (int j = i; j <= number; j += i) {
                numbers[j]++;
            }
        }

        int answer = 0;
        for (int i = 1; i <= number; i++) {
            answer += (numbers[i] > limit) ? power : numbers[i];
        }

        return answer;
    }
}

문제를 풀면서 시간 복잡도의 중요성을 절실히 느꼈다. 처음엔 각 기사 번호마다 직접 약수를 세는 방식으로 접근했는데, 이 방식은 직관적이지만 각 숫자마다 O(n)의 연산이 필요해 전체적으로 O(n²)의 시간 복잡도를 가진다. 입력값이 커질수록 실행 시간이 급격히 증가해 결국 시간 초과가 발생했다. 이를 해결하기 위해 약수의 성질을 활용한 효율적인 방법으로 접근했는데, 약수는 곧 배수의 관계로 연결된다는 점을 이용해 각 수의 배수에 대해 약수 개수를 누적하는 방식으로 구현했다. 이 방식은 O(n log n)의 시간 복잡도를 가지며 큰 입력값에서도 안정적으로 작동한다. 같은 문제라도 접근 방식에 따라 성능 차이가 극명하게 드러나며, 단순히 동작하는 코드보다 효율적인 알고리즘을 고민하는 것이 중요하다는 교훈을 얻었다.

 

-- 우유와 요거트가 담긴 장바구니
SELECT DISTINCT CY.CART_ID AS CART_ID
FROM CART_PRODUCTS CY
JOIN (
    SELECT CART_ID
    FROM CART_PRODUCTS
WHERE NAME = 'Milk'
) CM ON CY.CART_ID = CM.CART_ID
WHERE NAME = 'Yogurt'
ORDER BY 1;

-- 조회수가 가장 많은 중고거래 게시판의 첨부파일 조회하기
SELECT CONCAT('/home/grep/src/', F.BOARD_ID, '/', F.FILE_ID, F.FILE_NAME, F.FILE_EXT)AS FILE_PATH
FROM 
(
    SELECT BOARD_ID
    FROM USED_GOODS_BOARD
    ORDER BY VIEWS DESC
    LIMIT 1
) B
JOIN USED_GOODS_FILE F ON B.BOARD_ID = F.BOARD_ID
ORDER BY F.FILE_ID DESC;

-- 주문량이 많은 아이스크림들 조회하기
SELECT F.FLAVOR
FROM FIRST_HALF F
JOIN 
(
    SELECT FLAVOR, SUM(TOTAL_ORDER) AS TOTAL_ORDER
    FROM JULY
    GROUP BY FLAVOR
) J ON F.FLAVOR = J.FLAVOR
ORDER BY (F.TOTAL_ORDER + J.TOTAL_ORDER) DESC
LIMIT 3

서브쿼리를 활용한 SQL 문제 풀이를 하다 보면, 어느 순간부터 서브쿼리가 습관처럼 사용되고 있다는 느낌이 들 때가 있다. 물론 서브쿼리는 복잡한 조건을 분리하거나 가독성을 높이는 데 유용하지만, 모든 문제에 서브쿼리를 사용하는 것이 최선은 아니라는 생각이 들었다. 다양한 SQL 문법을 적극적으로 활용해보며 문제를 여러 각도에서 바라보는 연습을 해봐야겠다.

 

 

---