[프로그래머스/Kotlin]Lv3 - 억억단을 외우자

프로그래머스

문제

문제 설명

영우는 천하제일 암산대회를 앞두고 있습니다. 암산보다는 암기에 일가견이 있는 영우는 구구단을 확장하여 억억단을 만들고 외워버리기로 하였습니다.

억억단은 1억 x 1억 크기의 행렬입니다. 억억단을 외우던 영우는 친구 수연에게 퀴즈를 내달라고 부탁하였습니다.

수연은 평범하게 문제를 내봐야 영우가 너무 쉽게 맞히기 때문에 좀 어렵게 퀴즈를 내보려고 합니다. 적당한 수 e를 먼저 정하여 알려주고 e 이하의 임의의 수 s를 여러 개 얘기합니다. 영우는 각 s에 대해서 s보다 크거나 같고 e 보다 작거나 같은 수 중에서 억억단에서 가장 많이 등장한 수를 답해야 합니다. 만약 가장 많이 등장한 수가 여러 개라면 그 중 가장 작은 수를 답해야 합니다.

수연은 영우가 정답을 말하는지 확인하기 위해 당신에게 프로그램 제작을 의뢰하였습니다. e와 s의 목록 starts가 매개변수로 주어질 때 각 퀴즈의 답 목록을 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ e ≤ 5,000,000
• 1 ≤ starts의 길이 ≤ min {e,100,000}
• 1 ≤ starts의 원소 ≤ e
• starts에는 중복되는 원소가 존재하지 않습니다.

입출력 예

e	starts	result
8	[1,3,7]	[6,6,8]

입출력 예 설명

억억단에서 1 ~ 8이 등장하는 횟수는 다음과 같습니다.

1번 등장 : 1
2번 등장 : 2, 3, 5, 7
3번 등장 : 4
4번 등장 : 6, 8

[1, 8] 범위에서는 6과 8이 각각 4번씩 등장하여 가장 많은데 6이 더 작은 수이므로 6이 정답입니다.

[3, 8] 범위에서도 위와 같으므로 6이 정답입니다.

[7, 8] 범위에서는 7은 2번, 8은 4번 등장하므로 8이 정답입니다.

 

---

풀이

나의 풀이법

풀이 접근 과정

약수를 구하는 것에 초점을 뒀다.

그래서 약수를 구해 개수를 계산하고 해당 범위에서 최댓값을 구하면 될 것이라 생각했다.

class Solution {
    fun solution(e: Int, starts: IntArray): IntArray {
        val answer = IntArray(starts.size) { 0 }
        val counts = IntArray(e+1) { 0 }
        val max = IntArray(e+1) { 0 }

        var maxSum = 0
        for (i in e downTo 1) {
            for (j in e downTo 1) {
                if (i%j == 0) counts[i] += 1
            }

            if (counts[i] >= maxSum) {
                maxSum = counts[i]
                max[i] = i
            }
            else max[i] = max[i+1]
        }

        starts.forEachIndexed { index, i ->
            answer[index] = max[i]
        }

        return answer
    }
}

하지만 내가 약수를 구하는 데에서 시간 초과가 났고, 약수를 빠르게 구하는 법을 알아야했다.

그 부분은 질문하기 코드를 참고했다.

 

최종 소스코드

class Solution {
    fun solution(e: Int, starts: IntArray): IntArray {
        val answer = IntArray(starts.size) { 0 }

        val counts = IntArray(e+1) { 0 }
        val max = IntArray(e+1) { 0 }

        var maxSum = 0
        for (i in 1 .. e) {
            for (j in 1 .. e/i) {
                counts[i*j] += 1
            }
        }

        for (i in e downTo 1) {
            if (counts[i] >= maxSum) {
                maxSum = counts[i]
                max[i] = i
            }
            else max[i] = max[i+1]
        }

        starts.forEachIndexed { index, i ->
            answer[index] = max[i]
        }

        return answer
    }
}

1. 초기값 세팅

counts 배열과 max 배열을 초기화한다.

counts 배열은 각 숫자의 약수 개수를 저장하고, max 배열은 각 숫자의 최대 약수를 저장한다.

 

2. 약수 구하기

counts 배열을 채우기 위한 중첩된 루프를 사용하여 각 숫자의 약수 개수를 계산한다.

바깥쪽 루프(i 루프)는 1부터 e까지 순회하며, 안쪽 루프(j 루프)는 1부터 e/i까지 순회하여 i*j의 약수를 찾는다.

약수를 찾을 때마다 해당 약수의 개수를 counts 배열에 증가시킨다.

 

3. 최다로 많이 나온 값 구하기

역순으로 e부터 1까지 순회하면서, 현재 숫자의 약수 개수가 이전까지의 최대 약수 개수(maxSum)보다 크거나 같다면

최대 약수를 업데이트하고, 그렇지 않으면 이전 최대 약수를 사용한다.

 

4. answer 배열 구하기

starts 배열을 순회하면서 각 숫자에 대한 최대 약수를 answer 배열에 저장한다.

 

---

Comment

문제의 접근은 쉬웠고 정답에 근접하기까지는 시간이 오래 걸리지 않았다.

하지만 약수를 구하는 데에서 시간을 많이 잡아먹었다.

도저히 내가 처음 풀었던 방법 이외의 방법이 떠오르지 않아 결국 질문하기를 참고하였다…