(알고리즘) 기사단원의 무기 풀이

• 내가 생각을 했을 때에 기사 단원의 무기 문제의 핵심은 다음과 같았다
  
  1. 매개 변수 number의 인자의 약수가 아닌 1부터 number까지의 약수의 값을 더한 것
  2. 만약에 약수의 개수가 limit 값을 넘었을 경우 파워 값을 더한다
• 이 2개의 문제를 풀어야 한다고 생각했다

 

1. 우선 이 문제를 풀기 위해서 1부터 number까지의 배열을 정의 해주고 배열은 반복문을 돌면서 약수를 만드는 로직을 구현했다

fun solution(number: Int, limit: Int, power: Int): Int {
    var answer = 0
    val arr = IntArray(number){index -> index + 1}

    arr.forEachIndexed{ i, it ->
          answer += getPrime(it)
    }

    return answer
}

fun getPrime(num: Int): Int {
    var count = 1
    for(i in 1 until num){
        if(num % i == 0){
            count += 1
        }

    }
    return count
}

• 약수는 간단하게 생각하면 1 부터 num보다 작은 숫자 중에서 나마지가 0인 숫자를 구하면 되겠다고 생각해서 문제를 풀었다

2. 다음 약수의 개수가 limit을 초과할 경우 power의 값을 더해서 계산하면 끝!!

fun solution(number: Int, limit: Int, power: Int): Int {
    var answer = 0
    val arr = IntArray(number){index -> index + 1}

    arr.forEachIndexed{ i, it ->
    
    // limit을 확인 후에 power를 넣어주는 로직 구현
      if(getPrime(it) > limit){
          answer += power
      }else{
          answer += getPrime(it)
      }
    }


    return answer
}

인줄 알았는데 결과를 돌려보니까 시간 초과가 뜨더라...

 

왜 뜨나 봤더니 문제의 중심은 이 부분 이었다

... 저 형식이 가뜩이나 이중 반복문 형식이라 시간이 많이 걸리는 구조인데 10만번이라니... 다른 구조를 생각해봐야겠다

 

• 그래서 시간복잡도 문제를 해결하기 위해서 다음 2개 중 하나를 정리하기로 했다
  1. number를 인자로 받는 배열을 불러올까??  <- 해당 부분은 배열 내부 값을 확인 못하니까 탈락
  2. 약수를 구하는 반복문을 개조한다?? <- 이거 밖에 답이 안보인다 ㅜㅜ
• 그래서 약수를 구하는 반복문을 개조하기 위해서 약수를 어떤식으로 구하나 부터 다시 한번 찾아보았다
• 그러니 이런 방법이 있는거 아닌가 
  • n이라는 숫자가 있으면 이 숫자의 최대 약수 값은 √n
  • 이라는 것을 봤다 그러면 n의 제곱근을 구하고 그 제곱근에서 반복문을 돌려서 약수를 찾은 후에 n제곱근을 제곱한 값만 카운팅 하면 되는 거라고 생각을 했다
  • 실제로 이 방법이면 기존에 모든 부분을 다 돌아야 했던 반복문이 제곱근 만큼 줄으니까 시간적인 이득도 볼 거 같아 바로 실행에 옮겼다

fun getPrime(num: Int): Int {
    var count = 0

    for(i in 1..sqrt(num.toDouble()).toInt()){
        if(i * i == num){
            count++
        }else if(num % i == 0){
            count += 2
        }
    }

    return count
}

• Kotlin의 sqrt() 함수를 이용해주고 위에 조건만 추가해주니까 성공 하더라..

결론

• 문제 자체는 해결했어도 더 좋은 더 효율 적인 방법을 찾아보자!!