[프로그래머스] Swift - 억억단을 외우자

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

프로그래머스

 

2023.11.15 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

문제 조건

• 억억단은 1억 x 1억 크기의 2채원 배열이다. (구구단 표의 확장)
• e와 starts 배열이 주어진다.
• starts배열의 각 원소 s보다 크거나 같고 e보다 작거나 같은 수 중에서 억억단에서 가장 많이 등장하는 수를 배열에 담아서 리턴해야 한다.

 

e의 최대 크기가 5,000,000이고 starts의 길이도 최대 100,000이기 때문에 시간 초과를 계속 의식해야 했습니다.

 

우선 이 문제를 해결하기 위해서는 임의의 수 N이 억억단에서 등장하는 횟수를 구하는 방법을 찾아야 했습니다.

문제에서 이렇게 N의 예시들을 직접 소개해주고 있는데 여기서 패턴을 찾을 수 있습니다.

바로 억억단에서 N이 등장하는 횟수는 N의 약수의 개수와 같습니다.

 

3의 약수는 (1, 3)이므로 2개입니다. 따라서 억억단에서 2번 등장했습니다.

8의 약수는 (1,2,4,8)이므로 4개이빈다. 따라서 억억단에서 4번 등장했습니다.

 

어떻게 보면 당연합니다. 억억단 자체가 2개의 수를 곱한 값을 배열에 추가하는 방식이기 때문에 N이 억억단에 들어가려면 약수끼리 곱해져야 하기 때문입니다.

 

그렇다면 약수의 개수를 구하는 방법은 무엇일까요?

 

직접 1부터 N까지 반복문을 돌며 나누어 떨어지는 수가 나오면 카운트를 1 증가시켜 구할 수 있지만 e의 크기가 5,000,000이기 때문에 이렇게 모든 수들을 개별로 구하면 시간초과가 발생합니다.

 

따라서 최대한 적은 수의 반복문으로 모든 수의 약수의 개수를 구해야 합니다.

 

방법은 의외로 간단합니다.

    var count = Array(repeating: 0, count: e+1) // count[i]는 i의 약수의 개수
    
    for i in 1...e {
        for j in 1...e/i {
            count[i*j] += 1
        }
    }

 

count라는 배열을 만들고 이 배열에 약수의 개수를 저장합니다.

반복문을 돌며 임의의 수 N(=i*j)이 나오면 count 배열에서 1 증가시키는 방법입니다.

이 아이디어는 마치 소수를 구할 때 사용하는 알고리즘인 에라토스테네스의 체의 방식과 유사합니다.

에라토스테네스의 체에서는 각 원소를 0으로 제거하며 진행해 나가지만 여기서는 1씩 증가시켜 나간다는 점이 다릅니다.

 

이 과정을 모두 거치면 count[i]에는 i의 약수의 개수가 저장되게 됩니다.

 

한가지 주의할 점은

    for i in 1...e {
        for j in stride(from: i, through: e, by: i) {
            count[j] += 1
        }
    }

 

이렇게 작성해도 동일한 결과가 나오지만 시간 초과가 발생합니다.

(swift에서 stride를 처리하는 데 더 시간이 소요되는 것 같습니다.)

 

 

아무튼 약수의 개수를 구했기 때문에 이제 문제의 절반을 해결했습니다.

 

이제 s와 e 사이에서 가장 많이 등장하는 수를 구해야 합니다.

 

s가 담긴 starts 배열의 길이가 길기 때문에 모든 s마다 새로 값을 찾으면 무조건 시간초과가 발생합니다.

즉, 한번 모든 경우의 수를 구하고 (O(N)) starts를 돌며 이전에 구한 값에서 뽑아오는 방식을 사용해야 합니다.

 

여기서 DP를 활용할 수 있었습니다.

 

    var dp = Array(repeating: 0, count: e+1) // dp[i]는 i...e 범위의 수 중에서 억억단에서 가장 많이 등장한 수

 

이렇게 dp를 선언합니다.

다른 문제에서는 보통 0~K의 범위에서 최댓값을 구하고 K가 증가하는 방식이지만 이 문제에서는 반대입니다.

S~E까지에서 S가 증가하기 때문에 DP 배열 또한 제일 마지막 원소부터 채우게 됩니다.

 

dp[i]는 count[dp[i+1]] 보다 count[i]가 크거나 같다면 i가 되고 아니라면 dp[i+1]이 됩니다.

 

즉, i의 약수의 개수가 dp[i+1]의 약수의 개수보다 많으면 새 값으로 갱신하고 아니라면 이전 값인 dp[i+1]을 유지하는 것입니다.

 

count배열이 [0, 1, 2, 2, 3, 2, 4, 2, 4]라면

dp 배열은 [0, 6, 6, 6, 6, 6, 6, 8, 8] 이됩니다.

 

 

 

풀이

1. solution 함수 구현

fileprivate func solution(_ e:Int, _ starts:[Int]) -> [Int] {
    var count = Array(repeating: 0, count: e+1) // count[i]는 i의 약수의 개수
    
    for i in 1...e {
        for j in 1...e/i {
            count[i*j] += 1
        }
    }

    var dp = Array(repeating: 0, count: e+1) // dp[i]는 i...e 범위의 수 중에서 억억단에서 가장 많이 등장한 수
    
    dp[e] = e
    
    for i in stride(from: e-1, to: 0, by: -1) {
        if count[dp[i+1]] <= count[i] {
            dp[i] = i
        } else {
            dp[i] = dp[i+1]
        }
    }

    var result = [Int]()
    
    for start in starts {
        result.append(dp[start])
    }
    
    return result
}

 

 

 

 

마무리

시간 초과가 빡빡한 문제였습니다.

약수 개수 구하기, DP의 활용이 필요했습니다.