프로그래머스 LV.1 기사단원의 무기

솔직히 이 문제를 보고 너무 쉽다고 느꼈습니다.

이게 정답률이 이렇게나 낮다고...??

 

네... 오만이고 착각이었습니다. 역시 걸리는 시간초과... ㅠㅠ

 

그럼 문제를 뜯어보겠습니다.

 

요약하자면 

1. number까지의 약수의 갯수를 구하고

2. limit보다 크면 power, 작으면 number의 요소 --> 모두 더하기

 

실패 케이스 첫번째

 1. 첫번째 방법
 func solution(_ number:Int, _ limit:Int, _ power:Int) -> Int {
     
     // 해당 number의 약수의 갯수를 담는 배열을 만들고
     // 약수의 갯수가 limit을 넘어가지 않으면 배열의 모든 수를 더한다
     // 만약 약수의 갯수가 limit을 넘어가면 power로 변환 해준다
     
     var countArray: [Int] = []
     var result = 0
     
     for i in 1...number {
         var count = 0
         for j in 1...number {
             if i%j == 0 {
                 count += 1
                 print(count)
             }
         }
         countArray.append(count)
         print(countArray)
     }
     
     for k in countArray {
         if k >= limit {
             result += power
         } else {
             result += k
         }
     }
     
     print(countArray)
     return result
 }

 

여기서 실패한 이유는 무엇일까요?? 

저는 처음에 이중 for문과 for문이 있어서 시간초과가 난줄 알고 다시 한번 고쳐봤습니다.

 

실패케이스 두번째

func solution(_ number:Int, _ limit:Int, _ power:Int) -> Int {
     
     // 해당 number의 약수의 갯수를 담는 배열을 만들고
     // 약수의 갯수가 limit을 넘어가지 않으면 배열의 모든 수를 더한다
     // 만약 약수의 갯수가 limit을 넘어가면 power로 변환 해준다
     
     var countArray: [Int] = []
     var result = 0
     
     for i in 1...number {
         var count = 0
         for j in 1...number {
             if i%j == 0 {
                 count += 1
             }
         }
         countArray.append(count)
         
         if countArray.last! <= limit {
             result += countArray.last!
         } else {
             result += power
         }
     }
     print(countArray)
     return result
 }

 

역시나.. 시간초과로 실패했습니다. 

 

원인을 찾아보니 이중 for문으로 돌리는게 문제였습니다.

 

약수의 갯수를 찾는 방법으로는 여러 방법이 있습니다. 제곱근을 이용해도 되고, 에라토스테네스의 체를 이용해도 됩니다.

저는 에라토스테네스의 체를 이용해서 풀어봤습니다. 

일단 어떤 차이가 있는지 코드를 통해 보겠습니다.

 

func solution(_ number: Int, _ limit: Int, _ power: Int) -> Int {
    
    var countArray = Array(repeating: 0, count: number + 1)
    print(countArray)
    
    for i in 1...number {
        for j in stride(from: i, through: number, by: i) {
            countArray[j] += 1
        }
    }
    print(countArray)
    
    var secondCountArray: [Int] = []
   
    for i in 1...number {
        var count = 0
        for j in 1...number {
            if i % j == 0 {
                count += 1
            }
        }
        secondCountArray.append(count)
    }
    
    print(secondCountArray)
    
    return 0
}

/*
[0, 1, 2, 2, 3, 2]
[1, 2, 2, 3, 2]
*/

 

첫번째는 stride를 사용해서 약수의 갯수를 추가했고, 

두번째는 이중 for문으로 사용해서 풀었는데, 확실히 코드가 길고 하나씩 돌기 때문에 확실히 시간복잡도가 큰 것을 알 수 있습니다.

 

그렇다면 stride를 사용해서 적어주고 나머지 아래 코드를 만들어보겠습니다.

func solution(_ number: Int, _ limit: Int, _ power: Int) -> Int {
    
    var result = 0
    var countArray = Array(repeating: 0, count: number + 1)
    print(countArray)
    
    for i in 1...number {
        for j in stride(from: i, through: number, by: i) {
            countArray[j] += 1
        }
    }
    print(countArray)   // [0, 1, 2, 2, 3, 2]
    
    // 0번째 인덱스는 비어져있으니까 1 번째 인덱스부터 시작 하는 for문을 만들어 줍니다
    for j in 1...number {
    	// countArray[j]가 limit보다 작거나 같으면 더해줍니다.
    	if countArray[j] <= limit {
        	result += countArray[j]
            // countArray[j]가 크다며 power를 추가해줍니다.
        } else {
        	result += power
        }
    }
    
    return result
}

 

 

한줄 평: 더욱 열심히 하자... 코딩은 단련이다!! 화이팅