[Level 1] 기사단원의 무기 - 전처리

[내배캠 - 오늘의 문제]

https://school.programmers.co.kr/learn/courses/30/lessons/136798

프로그래머스

문제의 point1. 1부터 n(최대 100,000)까지의 순회하며 i가 가진 약수의 개수를 구한다.

문제의 point2. 각 개수가 limit 보다 크다면 power 값으로 대체해야함 이후 sum해서 return

 

0. 처음의 접근 방식 2중 for문을 돌며, O(N^2)의 로직을 돌림 -> 시간 초과

 

1. 약수를 구할 때, 제곱근을 이용하여 시간 단축시킴 O(N) * O(root(N)) -> 풀기 성공

// 테스트 11 〉	통과 (104.64ms, 59.6MB)
// 테스트 12 〉	통과 (115.07ms, 60.6MB)
import kotlin.math.sqrt

class Solution {
    fun solution(number: Int, limit: Int, power: Int): Int {
        val counts = MutableList(number) { 0 }

        // 1. 1부터 number까지 약수의 개수를 구한다.
        for (i in counts.indices) {
            counts[i] = measureCount(i + 1)
        }

        // 2. counts를 순회하며 limit를 넘는지 판단한다.
        counts.forEachIndexed { index, i ->
            // 2-1. limit를 넘으면 counts[i]를 power 값으로 바꾼다.
            if (i > limit) {
                counts[index] = power
            }
        }

        // 3. 변환된 counts의 sum을 반환한다.
        return counts.sum()
    }

    fun measureCount(num: Int): Int {
        val square = sqrt(num.toDouble())

        var count = 0
        for (i in 1..square.toInt()) { // 제곱근 까지 돌고 * 2
            if (num % i == 0) {
                count += 2
            }
        }

        // num이 16인 경우, 4가 2번 카운트 되었으므로 -- 해줘야한다.
        // square가 정수인지 판단해야함 -> 소수점이 0인지 체크
        if (square - square.toInt() == 0.0) { //
            count--
        }

        return count
    }
}

 

1, 2 차이 : https://github.com/rlaxodud214/CodingTest_Kotlin/commit/fffed662bb8408ca1cb8ed7201102cc8c41b24cd

 

2. 불필요한 로직 개선 -> 코드가 간결해졌지만, 시간은 크게 차이가 없었음

- 개선점 1. 불필요한 mutableList를 제거후 Int 타입으로 수정

- 개선점 2. count가 limit보다 큰지 작은지 그때 그때 판단해서 answer에 넣도록 수정

// 테스트 14 〉통과 (112.09ms, 59.6MB)

import kotlin.math.sqrt

class Solution {
    fun solution(number: Int, limit: Int, power: Int): Int {
        var answer = 0

        // 1. 1부터 number까지 약수의 개수를 구한다.
        for (i in 1 until number) {
            val square = sqrt(i.toDouble())
            var count = 0

            for (j in 1..square.toInt()) { // 제곱근 까지 돌고 * 2
                if (i % j == 0) {
                    count += 2
                }
            }
            // num이 16인 경우, 4가 2번 카운트 되었으므로 -- 해줘야한다.
            // square가 정수인지 판단해야함 -> 소수점이 0인지 체크
            if (square - square.toInt() == 0.0) { //
                count--
            }

            // 2. limit를 넘으면 power를 아니면 count를 누적한다.
            answer += if(count > limit) power else count
        }

        return answer
    }
}

 

2, 3 차이 : https://github.com/rlaxodud214/CodingTest_Kotlin/commit/51415102e8f80617edbb6a37f27acf9ced0925ec

 

3. 다른 사람의 풀이를 이해한 뒤, 리팩토링 2차(이해한 아이디어를 이용해서 재구현)

     -> 아이디어 : 1부터 10만 까지의 약수를 미리 계산해두고, 가져다 쓰기?! 말로 표현하기가 어렵다. 

          정리 - 모든 2의 배수는 2를 약수로 가지고 있으니 모든 2의 배수에 약수의 개수 +1을 해주는 아이디어였다.

           에라토스테네스 공식의 약수버전이라고 이해해도 될 것 같다.

// 모든 Case가 3ms 이내, 메모리는 당연히 증가함 66MB

class Solution {
    val measureCount = IntArray(100_000) { 0 }

    init {
        // i가 2일때, 모든 2의 배수에 + 1 (약수의 개수 + 1)
        for (i in 0..measureCount.size) {
            for (j in i until measureCount.size step(i + 1)) {
                measureCount[j]++
            }
        }
    }

    fun solution(number: Int, limit: Int, power: Int): Int {
        var answer = 0

        for (i in 0 until number) {
            answer += if (measureCount[i] > limit) {
            	power
            } else {
            	measureCount[i]
            }
        }

        return answer
    }
}

 

4. 느낀점

1부터 100,000까지 각 요소의 약수의 개수를 count 하는 데는 시간이 많이 소요되지 않았다.

훨씬 더 오래 걸릴 거라고 생각했었음,,,

 

새로운 아이디어? 새로운 시각을 얻은 것 같아 기뻤고, 재구현에 바로 성공해서 제대로 이해한 것 같아 다행이였다.