Kotlin/Algorithm Problems

<프로그래머스> 숫자 카드 나누기(Lv.2)

re트 2024. 1. 2. 09:50
728x90

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/%EC%88%AB%EC%9E%90%20%EC%B9%B4%EB%93%9C%20%EB%82%98%EB%88%84%EA%B8%B0

[프로그래머스]

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

 

즐겁게 휴식으로 새해를 시작하고 처음 푼 문제

아주 생각보다 가볍게 풀렸다.

숫자도 엄청 크고 그래서 쉽게 풀리지 않을 줄 알았는데 30분정도만에 푼 거 같다.

 

보자마자 먼저 숫자가 크기 때문에 2중 반복문을 쌩으로 주어진 입력 배열에다가 하면 안 되겠다는 생각이 들었다.

그리고 '카드들에 적힌 모든 숫자를 나눌 수 있거나 없거나'라는 조건이 있었기에 최대공약수가 생각이 났는데 조금 다르게 접근을 했다.

먼저 입력 배열을 정렬하고 함수를 만들어서 가장 작은 수의 약수들을 가져왔다.

무조건 이 약수들 안에서 입력 배열 원소를 모두 나눌 수 있는 값이 나와야하기 때문이다.

이건 2중 반복문을 돌려도 최소한으로 돌리기 위해 생각해낸 방법이었다.

그렇게 얻어낸 값을 이제 입력 배열과 순회하면서 이게 조건에 맞는 값이 될 수 있는가를 판별한 다음에 가장 큰 양의 정수인가를 또 체크해서 최종 변수에 넣어줬다.

조건에 맞지 않으면 continue를 써서 그냥 넘어가도록 했다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import kotlin.math.sqrt

class Solution {
    fun solution(arrayA: IntArray, arrayB: IntArray): Int {
        var answer: Int = 0
        val divisorA = calDivisor(arrayA.sorted()[0])
        val divisorB = calDivisor(arrayB.sorted()[0])

        for (divisor in divisorA) {
            val a = arrayA.filter { it % divisor != 0 }
            if (a.isNotEmpty()) continue

            val b = arrayB.filter { it % divisor == 0 }
            if (b.isNotEmpty()) continue

            answer = maxOf(answer, divisor)
        }

        for (divisor in divisorB) {
            val b = arrayB.filter { it % divisor != 0 }
            if (b.isNotEmpty()) continue

            val a = arrayA.filter { it % divisor == 0 }
            if (a.isNotEmpty()) continue

            answer = maxOf(answer, divisor)
        }

        return answer
    }

    private fun calDivisor(num: Int): List<Int> {
        val temp = mutableSetOf<Int>()
        for (i in 1..sqrt(num.toDouble()).toInt()) {
            if (num % i == 0) {
                temp += i
                temp += (num / i)
            }
        }
        
        return temp.sortedDescending().toList()
    }
}

 

다른 사람들의 풀이를 보는데 가장 눈에 들어온 건 fold와 all을 쓴 풀이였다.

최대공약수의 성질을 이용한 풀이였고 아주 심플했다.

나도 fold 함수를 떠올렸다면 최대공약수를 이용해 풀지 않았을까 싶다.

그리고 all도 마찬가지로 아직 많이 써보지 않아서 떠오르지 않는 함수인데 배열(리스트) 내의 모든 원소를 체크해야할 때 아주 유용하게 쓸 수 있을 거 같으니 잘 기억해두고 써먹어야겠다.(all을 보니까 any도 생각난다.)

반응형