프로그래머스 숫자 카드 나누기
https://school.programmers.co.kr/learn/courses/30/lessons/135807
최대공약수를 활용해서 문제를 해결해야 함
문제에서 제시한 2가지 조건을 잘 생각해보자
for (i in 1 until size) {
gcdA = GCD(gcdA, arrayA[i])
gcdB = GCD(gcdB, arrayB[i])
}
철수와 영희의 최대공약수를 각각 구해주는 것이 이 문제의 핵심 포인트이다.
조건에서 제시하는 첫 번째는 각자 가진 카드들에 적힌 모든 숫자를 나눌 수 있어야 한다는 것,
다음은 이제 서로의 가진 카드들이 해당 최대공약수를 통해서 나눠지는지를 확인해야 한다.
if (divisable(arrayB, gcdA)) {
answer = Math.max(answer, gcdA)
}
if (divisable(arrayA, gcdB)) {
answer = Math.max(answer, gcdB)
}
fun divisable(array: IntArray, target: Int): Boolean {
array.forEach {
if (it % target == 0) {
return false
}
}
return true
} // End of divisable
각자 서로의 카드 전체를 순회하면서, 최대공약수로 나눠지는지를 파악하고 하나라도 나눠진다면 false를 return 하도록 한다.
이 2개의 최대공약수를 통해서 결과값을 가질 수 있다. 모두 false가 된다면 답은 0이 된다.
class Solution {
fun solution(arrayA: IntArray, arrayB: IntArray): Int {
var answer = 0
var gcdA = arrayA[0]
var gcdB = arrayB[0]
// 각 배열의 최대공약수 구하기
val size = arrayA.size
for (i in 1 until size) {
gcdA = GCD(gcdA, arrayA[i])
gcdB = GCD(gcdB, arrayB[i])
}
// 서로의 배열을 나눌 수 있는지 없는지 확인하기
if (divisable(arrayB, gcdA)) {
answer = Math.max(answer, gcdA)
}
if (divisable(arrayA, gcdB)) {
answer = Math.max(answer, gcdB)
}
return answer
} // End of solution
// 최대공약수 구하는 메소드
fun GCD(a: Int, b: Int): Int {
if (a % b == 0) return b
return GCD(b, a % b)
} // End of GCD
fun divisable(array: IntArray, target: Int): Boolean {
array.forEach {
if (it % target == 0) {
return false
}
}
return true
} // End of divisable
} // End of Solution class