[프로그래머스] 숫자 카드 나누기 | kotlin

문제 설명

철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a의 값을 구하려고 합니다.

1. 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
2. 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a

예를 들어, 카드들에 10, 5, 20, 17이 적혀 있는 경우에 대해 생각해 봅시다. 만약, 철수가 [10, 17]이 적힌 카드를 갖고, 영희가 [5, 20]이 적힌 카드를 갖는다면 두 조건 중 하나를 만족하는 양의 정수 a는 존재하지 않습니다. 하지만, 철수가 [10, 20]이 적힌 카드를 갖고, 영희가 [5, 17]이 적힌 카드를 갖는다면, 철수가 가진 카드들의 숫자는 모두 10으로 나눌 수 있고, 영희가 가진 카드들의 숫자는 모두 10으로 나눌 수 없습니다. 따라서 철수와 영희는 각각 [10, 20]이 적힌 카드, [5, 17]이 적힌 카드로 나눠 가졌다면 조건에 해당하는 양의 정수 a는 10이 됩니다.

철수가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayA와 영희가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayB가 주어졌을 때, 주어진 조건을 만족하는 가장 큰 양의 정수 a를 return하도록 solution 함수를 완성해 주세요. 만약, 조건을 만족하는 a가 없다면, 0을 return 해 주세요.

---

풀이

1 ~ 각 배열의 최솟값으로 for문을 돌려서 조건에 맞는 값을 찾으려 했지만

class Solution {
    fun solution(arrayA: IntArray, arrayB: IntArray): Int {

        val minA = arrayA.minOrNull() ?:0
        val minB = arrayB.minOrNull() ?:0
        val divider: MutableList<Int> = mutableListOf()

        for (i in 1..minA) {
            if(arrayA.filter { it%i==0 }.size == arrayA.size){
                if(arrayB.filter { it%i!=0 }.size==arrayB.size){
                    divider.add(i)
                }
            }
        }
        for (i in 1..minB) {
            if(arrayB.filter { it%i==0 }.size == arrayB.size){
                if(arrayA.filter { it%i!=0 }.size==arrayA.size){
                    divider.add(i)
                }
            }
        }
        return divider.maxOrNull() ?: 0
    }
}

시간 초과..! 하지만 테스트케이스 대부분이 통과하였기 때문에 for문에 들어가는 값을 제한하면 되겠다고 생각했다.

최솟값이 아닌 최솟값의 약수로 제한하면 되겠다고 생각함.

import kotlin.math.sqrt

class Solution {
    fun solution(arrayA: IntArray, arrayB: IntArray): Int {

        val minA = arrayA.minOrNull() ?: 0
        val minB = arrayB.minOrNull() ?: 0
        var answer: Int = 0

        val sqrtA = sqrt(minA.toDouble()).toInt()
        val dividerA: MutableSet<Int> = mutableSetOf()

        for (i in 1..sqrtA) {
            if (minA % i == 0) {
                if (arrayA.filter { it % i == 0 }.size == arrayA.size) {
                    dividerA.add(i)
                }
                if (arrayA.filter { it % (minA / i) == 0 }.size == arrayA.size) {
                    dividerA.add(minA / i)
                }
            }
        }

        val sqrtB = sqrt(minB.toDouble()).toInt()
        val dividerB: MutableSet<Int> = mutableSetOf()

        for (i in 1..sqrtB) {
            if (minB % i == 0) {
                if (arrayB.filter { it % i == 0 }.size == arrayB.size) {
                    dividerB.add(i)
                }
                if (arrayB.filter { it % (minB / i) == 0 }.size == arrayB.size) {
                    dividerB.add(minB / i)
                }
            }
        }
        dividerA.forEach { divider ->
            if (arrayB.filter { it % divider != 0 }.size == arrayB.size) {
                if (answer < divider) {
                    answer = divider
                }
            }
        }
        dividerB.forEach { divider ->
            if (arrayA.filter { it % divider != 0 }.size == arrayA.size) {
                if (answer < divider) {
                    answer = divider
                }
            }
        }
        return answer
    }
}

풀렸다!

이때 약수를 구하는 방법은 이 게시물 참고하여 구현하였다.

 

문제 링크